Lower bounds for depth-three arithmetic circuits with small bottom fanin

DOI10.1007/s00037-016-0132-0zbMath1345.68161OpenAlexW2409282510MaRDI QIDQ301527

Chandan Saha, Neeraj Kayal

Publication date: 30 June 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5061/

zbMATH Keywords

lower boundsarithmetic circuitsdepth three

Mathematics Subject Classification ID

Related Items (4)

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 ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ A super-quadratic lower bound for depth four arithmetic circuits

Cites Work

• Unnamed Item
• 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
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• Arithmetic Circuits: A Chasm at Depth 3
• Improved Bounds for Reduction to Depth 4 and Depth 3
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• Arithmetic Circuits: A survey of recent results and open questions
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits
• Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
• Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• A super-polynomial lower bound for regular arithmetic formulas
• Affine projections of polynomials
• Approaching the Chasm at Depth Four
• Depth-3 arithmetic circuits over fields of characteristic zero

This page was built for publication: Lower bounds for depth-three arithmetic circuits with small bottom fanin