Derandomization from Algebraic Hardness
From MaRDI portal
Publication:5073523
DOI10.1137/20M1347395OpenAlexW2965653594MaRDI QIDQ5073523
Ramprasad Saptharishi, Noam Solomon, Zeyu Guo, Mrinal Kumar
Publication date: 3 May 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1905.00091
algebraic complexitypolynomial identity testinghitting set generatorshardness versus randomnessalgebraic circuit lower bounds
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A probabilistic remark on algebraic program testing
- Symbolic and algebraic computation. EUROSAM '79, an international symposium on symbolic and algebraic manipulation, Marseille, France, June 1979
- Hardness vs randomness
- Mathematical problems for the next century
- On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
- Marginal hitting sets imply super-polynomial lower bounds for permanent
- Some remarks on multiplicity codes
- Simple extractors for all min-entropies and a new pseudorandom generator
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Combinatorial Nullstellensatz
- Polynomials with Rational Coefficients Which are Hard to Compute
- Bootstrapping variables in algebraic circuits
- Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudo-random generators for all hardnesses
This page was built for publication: Derandomization from Algebraic Hardness
