Approaching the Chasm at Depth Four

DOI10.1145/2629541zbMath1321.68275OpenAlexW2079910744MaRDI QIDQ5501936

No author found.

Publication date: 14 August 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2629541

zbMATH Keywords

determinantlower boundspermanentpartial derivativesarithmetic circuitsfan-indepth-4 circuits

Mathematics Subject Classification ID

Related Items (33)

Lower Bounds for Sums of Powers of Low Degree Univariates ⋮ Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Multi-\(k\)-ic depth three circuit lower bound ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ On the Power of Homogeneous Depth 4 Arithmetic Circuits ⋮ Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ Unnamed Item ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ Random arithmetic formulas can be reconstructed efficiently ⋮ Lower bounds by Birkhoff interpolation ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ On the complexity of the permanent in various computational models ⋮ 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 ⋮ Unnamed Item ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Lower bounds for arithmetic circuits via the Hankel matrix ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ Towards Optimal Depth Reductions for Syntactically Multilinear Circuits ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Unnamed Item ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees ⋮ Unifying known lower bounds via geometric complexity theory

Cites Work

• Unnamed Item
• Unnamed Item
• Arithmetic circuits: the chasm at depth four gets wider
• Random arithmetic formulas can be reconstructed efficiently
• Lower bounds and separations for constant depth multilinear circuits
• The irreducibility of ladder determinantal varieties
• Lower bounds on arithmetic circuits via partial derivatives
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• Gröbner bases and Stanley decompositions of determinantal ideals
• Stirling's Approximation for n!: The Ultimate Short Proof?
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Ideals of generic minors
• Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• A super-polynomial lower bound for regular arithmetic formulas
• Affine projections of polynomials
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Depth-3 arithmetic circuits over fields of characteristic zero

This page was built for publication: Approaching the Chasm at Depth Four