Lower bounds for depth-three arithmetic circuits with small bottom fanin
From MaRDI portal
Publication:301527
DOI10.1007/s00037-016-0132-0zbMath1345.68161OpenAlexW2409282510MaRDI QIDQ301527
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/
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
