An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

DOI10.1137/151002423zbMath1359.68108OpenAlexW2592993021WikidataQ115525657 ScholiaQ115525657MaRDI QIDQ2968156

Neeraj Kayal, Srikanth Srinivasan, Chandan Saha, Nutan Limaye

Publication date: 10 March 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/151002423

zbMATH Keywords

depth-four circuitshomogeneous arithmetic formulasshifted partial derivatives

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits ⋮ Lower Bounds for Sums of Powers of Low Degree Univariates ⋮ Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ 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 ⋮ On the Power of Homogeneous Depth 4 Arithmetic Circuits ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Depth-4 lower bounds, determinantal complexity: a unified approach ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ 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 ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arithmetic circuits: the chasm at depth four gets wider
• Lower bounds and separations for constant depth multilinear circuits
• Lower bounds on arithmetic circuits via partial derivatives
• Stirling's Approximation for n!: The Ultimate Short Proof?
• Arithmetic Circuits: A Chasm at Depth 3
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Partial Derivatives in Arithmetic Complexity and Beyond
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic Circuits: A survey of recent results and open questions
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• A complexity theory based on Boolean algebra
• Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits
• Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• The limits of depth reduction for arithmetic formulas
• A super-polynomial lower bound for regular arithmetic formulas
• Breaking the quadratic barrier for 3-LCC's over the reals
• Jacobian hits circuits
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• Approaching the Chasm at Depth Four
• Multi-linear formulas for permanent and determinant are of super-polynomial size

This page was built for publication: An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas