A zero-one law for RP and derandomization of AM if NP is not small

DOI10.1016/j.ic.2009.02.002zbMath1167.68021OpenAlexW2122475800MaRDI QIDQ2389331

Philippe Moser, Russell Impagliazzo

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

zbMATH Keywords

derandomizationresource-bounded measure

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A zero-one SUBEXP-dimension law for BPP, Polylog depth, highness and lowness for E

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Martingale families and dimension in P
• Almost everywhere high nonuniform complexity
• Observations on measure and lowness for \(\Delta_ 2^ p\)
• The zero-one law holds for BPP
• Derandomizing Arthur-Merlin games under uniform assumptions
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Baire categories on small complexity classes and meager-comeager laws
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Randomness conservation inequalities; information and independence in mathematical theories
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Power from Random Strings
• Easiness assumptions and hardness tests: Trading time for zero error