The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In

DOI10.1137/140999220zbMath1330.68097arXiv1311.6716OpenAlexW1900995703MaRDI QIDQ3451754

Mrinal Kumar, Shubhangi Saraf

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

zbMATH Keywords

lower boundsarithmetic circuitsdepth reduction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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