Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
From MaRDI portal
Publication:3012845
DOI10.1007/978-3-642-22006-7_61zbMath1333.68123OpenAlexW1580127749MaRDI QIDQ3012845
Maurice Jansen, Rahul Santhanam
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_61
Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items
Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Interpolation in Valiant's theory
- The complexity of computing the permanent
- On defining integers and proving arithmetic circuit lower bounds
- Lower bounds and separations for constant depth multilinear circuits
- The complexity of combinatorial problems with succinct input representation
- The complexity of partial derivatives
- A probabilistic remark on algebraic program testing
- PRIMES is in P
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- On uniformity within \(NC^ 1\)
- Marginal hitting sets imply super-polynomial lower bounds for permanent
- PP is as Hard as the Polynomial-Time Hierarchy
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
- #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
- Complexity classes defined by counting quantifiers
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Depth-3 arithmetic circuits over fields of characteristic zero
