On the Power of Homogeneous Depth 4 Arithmetic Circuits

DOI10.1137/140999335zbMath1359.68110arXiv1404.1950OpenAlexW2594331892MaRDI QIDQ2968157

Mrinal Kumar, Shubhangi Saraf

Publication date: 10 March 2017

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

Full work available at URL: https://arxiv.org/abs/1404.1950

zbMATH Keywords

lower boundsdepth reductiondepth-4 circuitsshifted partial derivatives

Mathematics Subject Classification ID

Related Items (12)

Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits ⋮ Formulas versus Circuits for Small Distance Connectivity ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Unnamed Item ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ 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

• Arithmetic circuits: the chasm at depth four gets wider
• The complexity of partial derivatives
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Arithmetic Circuits: A Chasm at Depth 3
• Improved Bounds for Reduction to Depth 4 and Depth 3
• On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields
• Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• Fast Parallel Computation of Polynomials Using Few Processors
• Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits
• 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
• Approaching the Chasm at Depth Four
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Power of Homogeneous Depth 4 Arithmetic Circuits