Arithmetic Circuits: A Chasm at Depth 3

DOI10.1137/140957123zbMath1344.68300OpenAlexW2467589244MaRDI QIDQ2816300

No author found.

Publication date: 4 July 2016

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

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

zbMATH Keywords

determinantpermanentarithmetic circuitsdepth reductiondepth-3 circuits

Mathematics Subject Classification ID

Related Items (46)

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 ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Quadratic lower bounds for algebraic branching programs and formulas ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ Schur polynomials do not have small formulas if the determinant does not ⋮ Multi-\(k\)-ic depth three circuit lower bound ⋮ Testing the satisfiability of algebraic formulas over the field of two elements ⋮ Unnamed Item ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ 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 ⋮ Unnamed Item ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ The method of shifted partial derivatives cannot separate the permanent from the determinant ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Lower bounds by Birkhoff interpolation ⋮ Fundamental invariants of orbit closures ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Building above read-once polynomials: identity testing and hardness of representation ⋮ 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 ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ A quadratic lower bound for algebraic branching programs ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Unnamed Item ⋮ On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models ⋮ Unnamed Item ⋮ Lower bounds for matrix factorization ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits ⋮ A \(\tau \)-conjecture for Newton polygons ⋮ Geometric complexity theory: an introduction for geometers ⋮ Equivalence of polynomial identity testing and polynomial factorization ⋮ 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

• Arithmetic circuits: the chasm at depth four gets wider
• On computing the determinant in small parallel time using a small number of processors
• Lower bounds on arithmetic circuits via partial derivatives
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• Affine projections of symmetric polynomials.
• Characterizing Valiant's algebraic complexity classes
• Improved Bounds for Reduction to Depth 4 and Depth 3
• IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM
• The Power of Depth 2 Circuits over Algebras
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic Circuits: A survey of recent results and open questions
• Diagonal Circuit Identity Testing and Lower Bounds
• Fast Parallel Matrix Inversion Algorithms
• Sums of Like Powers of Multivariate Linear Forms
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• A super-polynomial lower bound for regular arithmetic formulas
• Tensor-Rank and Lower Bounds for Arithmetic Formulas
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• Approaching the Chasm at Depth Four
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Depth-3 arithmetic circuits over fields of characteristic zero
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Arithmetic Circuits: A Chasm at Depth 3