The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In
From MaRDI portal
Publication:3451754
DOI10.1137/140999220zbMath1330.68097arXiv1311.6716OpenAlexW1900995703MaRDI QIDQ3451754
Publication date: 18 November 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.6716
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (2)
On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models
Cites Work
- Unnamed Item
- Unnamed Item
- Arithmetic circuits: the chasm at depth four gets wider
- Improved bounds for reduction to depth 4 and depth 3
- Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
- Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication
- Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach
- Fast Parallel Computation of Polynomials Using Few Processors
- Arithmetic Circuits: A survey of recent results and open questions
- A super-polynomial lower bound for regular arithmetic formulas
- Reconstruction of depth-4 multilinear circuits with top fan-in 2
- Black-box identity testing of depth-4 multilinear circuits
- Approaching the Chasm at Depth Four
- Depth-3 arithmetic circuits over fields of characteristic zero
This page was built for publication: The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In
