A Selection of Lower Bounds for Arithmetic Circuits

DOI10.1007/978-3-319-05446-9_5zbMath1345.68162OpenAlexW2095780687MaRDI QIDQ2821696

Neeraj Kayal, Ramprasad Saptharishi

Publication date: 22 September 2016

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

Full work available at URL: https://doi.org/10.1007/978-3-319-05446-9_5

zbMATH Keywords

determinantlower boundspermanentarithmetic circuitsprimary

Mathematics Subject Classification ID

Related Items (2)

On the limits of depth reduction at depth 3 over small finite fields ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization

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
• The complexity of partial derivatives
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Hardness vs randomness
• Lower bounds on arithmetic circuits via partial derivatives
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Partial Derivatives in Arithmetic Complexity and Beyond
• Tensor-rank and lower bounds for arithmetic formulas
• 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 Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Faster Algebraic Algorithms for Path and Packing Problems
• A Lower Bound for the Formula Size of Rational Functions
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• A super-polynomial lower bound for regular arithmetic formulas
• Jacobian hits circuits
• Approaching the Chasm at Depth Four
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Depth-3 arithmetic circuits over fields of characteristic zero

This page was built for publication: A Selection of Lower Bounds for Arithmetic Circuits