More Like this

1. Proof Complexity Lower Bounds from Algebraic Circuit Complexity

   https://doi.org/10.4086/toc.2021.v017a010  

   Forbes, Michael A. ; Shpilka, Amir ; Tzameret, Iddo ; Wigderson, Avi ( January 2021 , Theory of Computing)

   Raz, Ran (Ed.)

   We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proof-complexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proof complexity bounds. These yield separations between IPS subsystems, which we complement by simulations to create a partial structure theory for IPS systems. Our first method is a functional lower bound, a notion of Grigoriev and Razborov, which is a function f' from n-bit strings to a field, such that any polynomial f agreeing with f' on the boolean cube requires large algebraic circuit complexity. We develop functional lower bounds for a variety of circuit classes (sparse polynomials, depth-3 powering formulas, read-once algebraic branching programs and multilinear formulas) where f'(x) equals 1/p(x) for a constant-degree polynomial p depending on the relevant circuit class. We believe these lower bounds are of independent interest in algebraic complexity, and show that they also imply lower bounds for the size of the corresponding IPS refutations for proving that the relevant polynomial p is non-zero over the boolean cube. In particular, we show super-polynomial lower bounds for refuting variants of the subset-sum axioms in these IPS subsystems. Our second method is to give lower bounds for multiples, that is, to give explicit polynomials whose all (non-zero) multiples require large algebraic circuit complexity. By extending known techniques, we give lower bounds for multiples for various restricted circuit classes such sparse polynomials, sums of powers of low-degree polynomials, and roABPs. These results are of independent interest, as we argue that lower bounds for multiples is the correct notion for instantiating the algebraic hardness versus randomness paradigm of Kabanets and Impagliazzo. Further, we show how such lower bounds for multiples extend to lower bounds for refutations in the corresponding IPS subsystem. 

   more » « less
2. 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
3. Lattice-Based Methods Surpass Sum-of-Squares in Clustering

   Ilias Zadik ; Min Jae Song ; Alexander S. Wein ; Joan Bruna ( July 2022 , conference on learning theory)

   Clustering is a fundamental primitive in unsupervised learning which gives rise to a rich class of computationally-challenging inference tasks. In this work, we focus on the canonical task of clustering d-dimensional Gaussian mixtures with unknown (and possibly degenerate) covariance. Recent works (Ghosh et al. ’20; Mao, Wein ’21; Davis, Diaz, Wang ’21) have established lower bounds against the class of low-degree polynomial methods and the sum-of-squares (SoS) hierarchy for recovering certain hidden structures planted in Gaussian clustering instances. Prior work on many similar inference tasks portends that such lower bounds strongly suggest the presence of an inherent statistical-to-computational gap for clustering, that is, a parameter regime where the clustering task is statistically possible but no polynomial-time algorithm succeeds. One special case of the clustering task we consider is equivalent to the problem of finding a planted hypercube vector in an otherwise random subspace. We show that, perhaps surprisingly, this particular clustering model does not exhibit a statistical-to-computational gap, despite the aforementioned low-degree and SoS lower bounds. To achieve this, we give an algorithm based on Lenstra–Lenstra–Lovász lattice basis reduction which achieves the statistically-optimal sample complexity of d + 1 samples. This result extends the class of problems whose conjectured statistical-to-computational gaps can be “closed” by “brittle” polynomial-time algorithms, highlighting the crucial but subtle role of noise in the onset of statistical-to-computational gaps. 

   more » « less
4. Brief Announcement: Relations Between Space-Bounded and Adaptive Massively Parallel Computations

   https://doi.org/10.4230/LIPIcs.DISC.2023.37  

   Chen, Michael ; Pavan, A ; Vinodchandran, N V ( October 2023 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Oshman, Rotem (Ed.)

   In this work, we study the class of problems solvable by (deterministic) Adaptive Massively Parallel Computations in constant rounds from a computational complexity theory perspective. A language L is in the class AMPC⁰ if, for every ε > 0, there is a deterministic AMPC algorithm running in constant rounds with a polynomial number of processors, where the local memory of each machine s = O(N^ε). We prove that the space-bounded complexity class ReachUL is a proper subclass of AMPC⁰. The complexity class ReachUL lies between the well-known space-bounded complexity classes Deterministic Logspace (DLOG) and Nondeterministic Logspace (NLOG). In contrast, we establish that it is unlikely that PSPACE admits AMPC algorithms, even with polynomially many rounds. We also establish that showing PSPACE is a subclass of nonuniform-AMPC with polynomially many rounds leads to a significant separation result in complexity theory, namely PSPACE is a proper subclass of EXP^{Σ₂^{𝖯}}. 

   more » « less
5. On edge‐ordered Ramsey numbers

   https://doi.org/10.1002/rsa.20954  

   Fox, Jacob ; Li, Ray ( September 2020 , Random Structures & Algorithms)

   An edge‐ordered graph is a graph with a linear ordering of its edges. Two edge‐ordered graphs areequivalentif there is an isomorphism between them preserving the edge‐ordering. Theedge‐ordered Ramsey number r_edge(H; q) of an edge‐ordered graphHis the smallestNsuch that there exists an edge‐ordered graphGonNvertices such that, for everyq‐coloring of the edges ofG, there is a monochromatic subgraph ofGequivalent toH. Recently, Balko and Vizer proved thatr_edge(H; q) exists, but their proof gave enormous upper bounds on these numbers. We give a new proof with a much better bound, showing there exists a constantcsuch thatfor every edge‐ordered graphHonnvertices. We also prove a polynomial bound for the edge‐ordered Ramsey number of graphs of bounded degeneracy. Finally, we prove a strengthening for graphs where every edge has a label and the labels do not necessarily have an ordering.

    

   more » « less