A zero-one law for RP and derandomization of AM if NP is not small
From MaRDI portal
Publication:2389331
DOI10.1016/J.IC.2009.02.002zbMATH Open1167.68021OpenAlexW2122475800MaRDI QIDQ2389331FDOQ2389331
Authors: Russell Impagliazzo, Philippe Moser 
Publication date: 15 July 2009
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://eprints.maynoothuniversity.ie/8245/1/PM-Zero-2009.pdf
Recommendations
- scientific article; zbMATH DE number 1670468
- On uniform amplification of hardness in NP
- A Note on Randomized Polynomial Time
- On circuit lower bounds from derandomization
- Publication:4938630
- Computing and Combinatorics
- Satisfiability and derandomization for small polynomial threshold circuits
- Round Complexity of Common Randomness Generation: The Amortized Setting
- Hardness amplification within NP against deterministic algorithms
- Relative to a random oracle, NP is not small
Cites Work
- Title not available (Why is that?)
- Randomness conservation inequalities; information and independence in mathematical theories
- Almost everywhere high nonuniform complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Easiness assumptions and hardness tests: Trading time for zero error
- Observations on measure and lowness for \(\Delta_ 2^ p\)
- The zero-one law holds for BPP
- Power from Random Strings
- Martingale families and dimension in P
- Derandomizing Arthur-Merlin games under uniform assumptions
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Baire categories on small complexity classes and meager-comeager laws
Cited In (2)
This page was built for publication: A zero-one law for RP and derandomization of AM if NP is not small
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2389331)
