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