Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
From MaRDI portal
Publication:1941704
DOI10.1016/j.ipl.2012.08.001zbMath1259.68073MaRDI QIDQ1941704
Publication date: 21 March 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2012.08.001
computational complexity; lower bounds; permanent; derandomization; arithmetic circuits; polynomial identity testing
68Q25: Analysis of algorithms and problem complexity
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68W20: Randomized algorithms
Cites Work
- Unnamed Item
- Interpolation in Valiant's theory
- On defining integers and proving arithmetic circuit lower bounds
- On computing the determinant in small parallel time using a small number of processors
- The complexity of combinatorial problems with succinct input representation
- On uniform circuit complexity
- A probabilistic remark on algebraic program testing
- Hardness vs randomness
- The complexity of factors of multivariate polynomials
- The complexity of constructing pseudorandom generators from hard functions
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- The complexity of matrix rank and feasible systems of linear equations
- Cook's versus Valiant's hypothesis
- Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
- Combinatorial Nullstellensatz
- 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
