Depth-3 arithmetic circuits over fields of characteristic zero
From MaRDI portal
Publication:5957088
DOI10.1007/PL00001609zbMath0998.68064MaRDI QIDQ5957088
Publication date: 28 February 2002
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00001609
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, A super-quadratic lower bound for depth four arithmetic circuits, Approaching the Chasm at Depth Four, Schur polynomials do not have small formulas if the determinant does not, Lower bounds for depth-three arithmetic circuits with small bottom fanin, Lower bounds for the determinantal complexity of explicit low degree polynomials, Homogeneous formulas and symmetric polynomials, Deterministic polynomial identity tests for multilinear bounded-read formulae, Resolution over linear equations and multilinear proofs, Monotone separations for constant degree polynomials, Affine projections of symmetric polynomials., Small space analogues of Valiant's classes and the limitations of skew formulas, Limitations of sums of bounded read formulas and ABPs, Quadratic lower bounds for algebraic branching programs and formulas, On \(\epsilon\)-sensitive monotone computations, Average-case linear matrix factorization and reconstruction of low width algebraic branching programs, Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees, Geometric complexity theory: an introduction for geometers, Unifying known lower bounds via geometric complexity theory, On the limits of depth reduction at depth 3 over small finite fields, Arithmetic Circuits: A Chasm at Depth 3, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits, A Selection of Lower Bounds for Arithmetic Circuits, Types of depth and formula size, Uniform derandomization from pathetic lower bounds, The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials, On the Expressive Power of Read-Once Determinants, Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth, Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials, The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In
