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.68073OpenAlexW2068275484MaRDI 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 complexitylower boundspermanentderandomizationarithmetic circuitspolynomial identity testing
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
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
This page was built for publication: Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
