A Selection of Lower Bounds for Arithmetic Circuits

DOI10.1007/978-3-319-05446-9_5MaRDI QIDQ2821696zbMATH OpenOpenAlexFDO

Authors 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

arithmetic circuitsdeterminantlower boundspermanentprimary

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Cites work

• A Lower Bound for the Formula Size of Rational Functions
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• A super-polynomial lower bound for regular arithmetic formulas
• Approaching the chasm at depth four
• Arithmetic circuits: a survey of recent results and open questions
• Arithmetic circuits: the chasm at depth four gets wider
• Arithmetic complexity in ring extensions
• Computing polynomials with few multiplications
• Depth-3 arithmetic circuits over fields of characteristic zero
• Depth-4 lower bounds, determinantal complexity: a unified approach
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• Fast Parallel Computation of Polynomials Using Few Processors
• Faster Algebraic Algorithms for Path and Packing Problems
• Hardness vs randomness
• scientific article; zbMATH DE number 1775446 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Jacobian hits circuits: hitting-sets, lower bounds for depth-\(D\) occur-\(k\) formulas \& depth-\(3\) transcendence degree-\(k\) circuits
• Lower bounds and separations for constant depth multilinear circuits
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• Lower bounds on arithmetic circuits via partial derivatives
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Partial derivatives in arithmetic complexity and beyond
• Separation of multilinear circuit and formula size
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Tensor-rank and lower bounds for arithmetic formulas
• The complexity of partial derivatives

Cited in

(10)

• Circuits in bounded arithmetic. I
• On the limits of depth reduction at depth 3 over small finite fields
• Some lower bound results for set-multilinear arithmetic computations
• Geometric complexity theory. V: Efficient algorithms for Noether normalization
• On Lower Bounds for Constant Width Arithmetic Circuits
• Lower bounds for modular counting by circuits with modular gates
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
• On defining integers and proving arithmetic circuit lower bounds
• Symmetric arithmetic circuits
• Symmetric arithmetic circuits

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

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