Arithmetic circuits: the chasm at depth four gets wider
From MaRDI portal
Publication:442109
DOI10.1016/j.tcs.2012.03.041zbMath1253.68139OpenAlexW2016576580MaRDI QIDQ442109
Publication date: 9 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.041
Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (40)
The arithmetic complexity of tensor contraction ⋮ Lower Bounds for Sums of Powers of Low Degree Univariates ⋮ Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In ⋮ On the limits of depth reduction at depth 3 over small finite fields ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ Log-Concavity and Lower Bounds for Arithmetic Circuits ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Shadows of Newton polytopes ⋮ Multi-\(k\)-ic depth three circuit lower bound ⋮ Equations for secant varieties of Chow varieties ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ On the Power of Homogeneous Depth 4 Arithmetic Circuits ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ The method of shifted partial derivatives cannot separate the permanent from the determinant ⋮ Lower bounds by Birkhoff interpolation ⋮ Unnamed Item ⋮ Depth-4 lower bounds, determinantal complexity: a unified approach ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Improved bounds for reduction to depth 4 and depth 3 ⋮ Lower bounds for matrix factorization ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ Towards Optimal Depth Reductions for Syntactically Multilinear Circuits ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Unnamed Item ⋮ Lower bounds for matrix factorization ⋮ Approaching the Chasm at Depth Four ⋮ A \(\tau \)-conjecture for Newton polygons ⋮ Geometric complexity theory: an introduction for geometers ⋮ Unifying known lower bounds via geometric complexity theory ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds and separations for constant depth multilinear circuits
- Properties that characterize LOGCFL
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- On arithmetic branching programs
- Balancing syntactically multilinear arithmetic circuits
- Characterizing Valiant's algebraic complexity classes
- Fast Parallel Computation of Polynomials Using Few Processors
- On the Power of Small-Depth Computation
- A Survey of Lower Bounds for Satisfiability and Related Problems
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- Expressing a fraction of two determinants as a determinant
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
This page was built for publication: Arithmetic circuits: the chasm at depth four gets wider
