skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Low-Depth Algebraic Circuit Lower Bounds over Any Field
The recent breakthrough of Limaye, Srinivasan and Tavenas [Limaye et al., 2022] (LST) gave the first super-polynomial lower bounds against low-depth algebraic circuits, for any field of zero (or sufficiently large) characteristic. It was an open question to extend this result to small-characteristic ([Limaye et al., 2022; Govindasamy et al., 2022; Fournier et al., 2023]), which in particular is relevant for an approach to prove superpolynomial AC⁰[p]-Frege lower bounds ([Govindasamy et al., 2022]). In this work, we prove super-polynomial algebraic circuit lower bounds against low-depth algebraic circuits over any field, with the same parameters as LST (or even matching the improved parameters of Bhargav, Dutta, and Saxena [Bhargav et al., 2022]). We give two proofs. The first is logical, showing that even though the proof of LST naively fails in small characteristic, the proof is sufficiently algebraic that generic transfer results imply the result over characteristic zero implies the result over all fields. Motivated by this indirect proof, we then proceed to give a second constructive proof, replacing the field-dependent set-multilinearization result of LST with a set-multilinearization that works over any field, by using the Binet-Minc identity [Minc, 1979].  more » « less
Award ID(s):
2047310
PAR ID:
10609591
Author(s) / Creator(s):
Editor(s):
Santhanam, Rahul
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Volume:
300
ISSN:
1868-8969
ISBN:
978-3-95977-331-7
Page Range / eLocation ID:
31:1-31:16
Subject(s) / Keyword(s):
algebraic circuits lower bounds low-depth circuits positive characteristic Theory of computation → Algebraic complexity theory
Format(s):
Medium: X Size: 16 pages; 776736 bytes Other: application/pdf
Size(s):
16 pages 776736 bytes
Right(s):
Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, 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. ; ; (, LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science)
    A major open problem in proof complexity is to prove superpolynomial lower bounds for AC0[p]-Frege proofs. This system is the analog of AC0 [p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years ([28, 30]), there are no significant lower bounds for AC0 [p]-Frege. Significant and extensive degree lower bounds have been obtained for a variety of subsystems of AC0[p]-Frege, including Nullstellensatz ([3]), Polynomial Calculus ([9]), and SOS ([14]). However to date there has been no progress on AC0 [p]-Frege lower bounds. In this paper we study constant-depth extensions of the Polynomial Calculus [13]. We show that these extensions are much more powerful than was previously known. Our main result is that small depth (≤ 43) Polynomial Calculus (over a sufficiently large field) can polynomially effectively simulate all of the well-studied semialgebraic proof systems: Cutting Planes, Sherali-Adams, Sum-of-Squares (SOS), and Positivstellensatz Calculus (Dynamic SOS). Additionally, they can also quasi-polynomially effectively simulate AC0[q]-Frege for any prime q independent of the characteristic of the underlying field. They can also effectively simulate TC0-Frege if the depth is allowed to grow proportionally. Thus, proving strong lower bounds for constant-depth extensions of Polynomial Calculus would not only give lower bounds for AC0 [p]-Frege, but also for systems as strong as TC0-Frege. 
    more » « less
  3. ; ; ; ; (, 50th International Colloquium on Automata, Languages, and Programming)
    Etessami, Kousha; Feige, Uriel; Puppis, Gabriele (Ed.)
    A recent breakthrough work of Limaye, Srinivasan and Tavenas [Nutan Limaye et al., 2021] proved superpolynomial lower bounds for low-depth arithmetic circuits via a "hardness escalation" approach: they proved lower bounds for low-depth set-multilinear circuits and then lifted the bounds to low-depth general circuits. In this work, we prove superpolynomial lower bounds for low-depth circuits by bypassing the hardness escalation, i.e., the set-multilinearization, step. As set-multilinearization comes with an exponential blow-up in circuit size, our direct proof opens up the possibility of proving an exponential lower bound for low-depth homogeneous circuits by evading a crucial bottleneck. Our bounds hold for the iterated matrix multiplication and the Nisan-Wigderson design polynomials. We also define a subclass of unrestricted depth homogeneous formulas which we call unique parse tree (UPT) formulas, and prove superpolynomial lower bounds for these. This significantly generalizes the superpolynomial lower bounds for regular formulas [Neeraj Kayal et al., 2014; Hervé Fournier et al., 2015]. 
    more » « less
  4. ; ; (, Quantum)
    The stabilizer rank of a quantum state ψ is the minimal r such that | ψ ⟩ = ∑ j = 1 r c j | φ j ⟩ for c j ∈ C and stabilizer states φ j . The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n -th tensor power of single-qubit magic states.We prove a lower bound of Ω ( n ) on the stabilizer rank of such states, improving a previous lower bound of Ω ( n ) of Bravyi, Smith and Smolin \cite{BSS16}. Further, we prove that for a sufficiently small constant δ , the stabilizer rank of any state which is δ -close to those states is Ω ( n / log ⁡ n ) . This is the first non-trivial lower bound for approximate stabilizer rank.Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of F 2 n , and we use tools from analysis of boolean functions and complexity theory. The proof of the first result involves a careful analysis of directional derivatives of quadratic polynomials, whereas the proof of the second result uses Razborov-Smolensky low degree polynomial approximations and correlation bounds against the majority function. 
    more » « less
  5. ; ; (, Mathematische Zeitschrift)
    We prove new results of Mattila–Sjölin type, giving lower bounds on Hausdorff dimensions of thin sets E ⊂ R^d ensuring that various k-point configuration sets, generated by elements of E , have nonempty interior. The dimensional thresholds in our previous work (Greenleaf et al., Mathematika 68(1):163–190, 2022) were dictated by associating to a configuration function a family of generalized Radon transforms, and then optimizing L^2-Sobolev estimates for them over all nontrivial bipartite partitions of the k points. In the current work, we extend this by allowing the optimization to be done locally over the configuration’s incidence relation, or even microlocally over the conormal bundle of the incidence relation. We use this approach to prove Mattila–Sjölin type results for (i) areas of subtriangles determined by quadrilaterals and pentagons in a set E ⊂ R^2; (ii) pairs of ratios of distances of 4-tuples in R^d; and (iii) similarity classes of triangles in R^d, as well as to (iv) give a short proof of Palsson and Romero Acosta’s result on congruence classes of triangles in R . 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email