More Like this

1. Point-hyperplane Incidence Geometry and the Log-rank Conjecture

   https://doi.org/10.1145/3543684  

   Singer, Noah; Sudan, Madhu (June 2022, ACM Transactions on Computation Theory)

   We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in ℝ d that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., 2 –polylog( d ) ) fraction of the incidences, in the sense of containing a large fraction of the points and being contained in a large fraction of the hyperplanes. In other words, the point-hyperplane incidence graph for such configurations has a large complete bipartite subgraph. Alternatively, our conjecture may be interpreted linear-algebraically as follows: Any rank- d matrix containing at most O (1) distinct entries in each column contains a submatrix of fractional size 2 –polylog( d ) , in which each column is constant. We prove that our conjecture is equivalent to the log-rank conjecture; the crucial ingredient of this proof is a reduction from bounds for parallel k -partitions to bounds for parallel ( k -1)-partitions. We also introduce an (apparent) strengthening of the conjecture, which relaxes the requirements that the sets of hyperplanes be parallel. Motivated by the connections above, we revisit well-studied questions in point-hyperplane incidence geometry without structural assumptions (i.e., the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density Ω (ε 2 d / d ) in any d -dimensional configuration with incidence density ε, qualitatively matching previous results proved using sophisticated geometric techniques. We also improve an upper-bound construction of Apfelbaum and Sharir [ 2 ], yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is Ω (1/√ d ). Finally, we discuss various constructions (due to others) of products of Boolean matrices which yield configurations with incidence density Ω (1) and complete bipartite subgraph density 2 -Ω (√ d ) , and pose several questions for this special case in the alternative language of extremal set combinatorics. Our framework and results may help shed light on the difficulty of improving Lovett’s Õ(√ rank( f )) bound [ 20 ] for the log-rank conjecture. In particular, any improvement on this bound would imply the first complete bipartite subgraph size bounds for parallel 3-partitioned configurations which beat our generic bounds for unstructured configurations. 

   more » « less
2. Purity and Separation for Oriented Matroids

   https://doi.org/10.1090/memo/1439  

   Galashin, Pavel; Postnikov, Alexander (September 2023, Memoirs of the American Mathematical Society)

   Leclerc and Zelevinsky, motivated by the study of quasi-commuting quantum flag minors, introduced the notions of strongly separated and weakly separated collections. These notions are closely related to the theory of cluster algebras, to the combinatorics of the double Bruhat cells, and to the totally positive Grassmannian. A key feature, called the purity phenomenon, is that every maximal by inclusion strongly (resp., weakly) separated collection of subsets in $[n]$ has the same cardinality. In this paper, we extend these notions and define $$\mathcal{M}$$-separated collections for any oriented matroid $$\mathcal{M}$$. We show that maximal by size $$\mathcal{M}$$-separated collections are in bijection with fine zonotopal tilings (if $$\mathcal{M}$$ is a realizable oriented matroid), or with one-element liftings of $$\mathcal{M}$$ in general position (for an arbitrary oriented matroid). We introduce the class of pure oriented matroids for which the purity phenomenon holds: an oriented matroid $$\mathcal{M}$$ is pure if $$\mathcal{M}$$-separated collections form a pure simplicial complex, i.e., any maximal by inclusion $$\mathcal{M}$$-separated collection is also maximal by size. We pay closer attention to several special classes of oriented matroids: oriented matroids of rank $$3$$, graphical oriented matroids, and uniform oriented matroids. We classify pure oriented matroids in these cases. An oriented matroid of rank $$3$$ is pure if and only if it is a positroid (up to reorienting and relabeling its ground set). A graphical oriented matroid is pure if and only if its underlying graph is an outerplanar graph, that is, a subgraph of a triangulation of an $$n$$-gon. We give a simple conjectural characterization of pure oriented matroids by forbidden minors and prove it for the above classes of matroids (rank $$3$$, graphical, uniform). 

   more » « less
3. Leibniz International Proceedings in Informatics (LIPIcs):38th Computational Complexity Conference (CCC 2023)

   https://doi.org/10.4230/LIPIcs.CCC.2023.4  

   Galesi, Nicola; Grochow, Joshua A.; Pitassi, Toniann; She, Adrian (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ta-Shma, Amnon (Ed.)

   The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, TI (or rather, proving that two tensors are non-isomorphic) lends itself very naturally to algebraic and semi-algebraic proof systems, such as the Polynomial Calculus (PC) and Sum of Squares (SoS). For its combinatorial cousin Graph Isomorphism, essentially optimal lower bounds are known for approaches based on PC and SoS (Berkholz & Grohe, SODA '17). Our main results are an Ω(n) lower bound on PC degree or SoS degree for Tensor Isomorphism, and a nontrivial upper bound for testing isomorphism of tensors of bounded rank. We also show that PC cannot perform basic linear algebra in sub-linear degree, such as comparing the rank of two matrices (which is essentially the same as 2-TI), or deriving BA=I from AB=I. As linear algebra is a key tool for understanding tensors, we introduce a strictly stronger proof system, PC-Inv, which allows as derivation rules all substitution instances of the implication AB=I → BA=I. We conjecture that even PC-Inv cannot solve TI in polynomial time either, but leave open getting lower bounds on PC-Inv for any system of equations, let alone those for TI. We also highlight many other open questions about proof complexity approaches to TI. 

   more » « less
4. New hardness results for planar graph problems in p and an algorithm for sparsest cut

   https://doi.org/10.1145/3357713.3384310  

   Abboud, Amir; Cohen-Addad, Vincent; Klein, Philip N. (June 2020, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing)

   null (Ed.)

   The Sparsest Cut is a fundamental optimization problem that have been extensively studied. For planar inputs the problem is in P and can be solved in Õ(n 3 ) time if all vertex weights are 1. Despite a significant amount of effort, the best algorithms date back to the early 90’s and can only achieve O(log n)-approximation in Õ(n) time or 3.5-approximation in Õ(n 2 ) time [Rao, STOC92]. Our main result is an Ω(n 2−ε ) lower bound for Sparsest Cut even in planar graphs with unit vertex weights, under the (min, +)-Convolution conjecture, showing that approxima- tions are inevitable in the near-linear time regime. To complement the lower bound, we provide a 3.3-approximation in near-linear time, improving upon the 25-year old result of Rao in both time and accuracy. We also show that our lower bound is not far from optimal by observing an exact algorithm with running time Õ(n 5/2 ) improving upon the Õ(n 3 ) algorithm of Park and Phillips [STOC93]. Our lower bound accomplishes a repeatedly raised challenge by being the first fine-grained lower bound for a natural planar graph problem in P. Building on our construction we prove near-quadratic lower bounds under SETH for variants of the closest pair problem in planar graphs, and use them to show that the popular Average-Linkage procedure for Hierarchical Clustering cannot be simulated in truly subquadratic time. At the core of our constructions is a diamond-like gadget that also settles the complexity of Diameter in distributed planar networks. We prove an Ω(n/ log n) lower bound on the number of communication rounds required to compute the weighted diameter of a network in the CONGET model, even when the underlying graph is planar and all nodes are D = 4 hops away from each other. This is the first poly(n) lower bound in the planar-distributed setting, and it complements the recent poly(D, log n) upper bounds of Li and Parter [STOC 2019] for (exact) unweighted diameter and for (1 + ε) approximate weighted diameter. 

   more » « less
5. The Combinatorics Behind the Leading Kazhdan-Lusztig Coefficients of Braid Matroids

   https://doi.org/10.37236/12778  

   Gao, Alice LL; Proudfoot, Nicholas James; Yang, Arthur LB; Zhang, Zhong-Xue (July 2024, The Electronic Journal of Combinatorics)

   Ferroni and Larson gave a combinatorial interpretation of the braid Kazhdan-Lusztig polynomials in terms of series-parallel matroids. As a consequence, they confirmed an explicit formula for the leading Kazhdan-Lusztig coefficients of braid matroids with odd rank, as conjectured by Elias, Proudfoot, and Wakefield. Based on Ferroni and Larson’s work, we further explore the combinatorics behind the leading Kazhdan-Lusztig coefficients of braid matroids. The main results of this paper include an explicit formula for the leading Kazhdan-Lusztig coefficients of braid matroids with even rank, a simple expression for the number of simple series-parallel matroids of rank $k + 1$ on $2k$ elements, and explicit formulas for the leading coefficients of inverse Kazhdan-Lusztig polynomials of braid matroids. The binomial identity for the Abel polynomials plays an important role in the proofs of these formulas. 

   more » « less