Lower bounds for depth three arithmetic circuits with small bottom fanin

DOI10.4230/LIPICS.CCC.2015.158MaRDI QIDQ4601827zbMATH OpenFDO

Authors Neeraj Kayal, Chandan Saha

Publication date 24 January 2018

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2015.158

zbMATH Keywords

arithmetic circuitsbottom fan-indepth-three circuitslower bound

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• Depth-3 arithmetic circuits over fields of characteristic zero
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• The computational power of depth five arithmetic circuits
• scientific article; zbMATH DE number 1775446

Cited in

(10)

• On \(\varSigma\wedge\varSigma\wedge\varSigma\) circuits: the role of middle \(\varSigma\) fan-in, homogeneity and bottom degree
• Multi-k-ic depth three circuit lower bound
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• Lower bounds for sums of powers of low degree univariates
• “Resistant” Polynomials and Stronger Lower Bounds for Depth-Three Arithmetical Formulas
• An almost cubic lower bound for depth three arithmetic circuits
• The computational power of depth five arithmetic circuits
• A super-quadratic lower bound for depth four arithmetic circuits
• The limits of depth reduction for arithmetic formulas
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601827)