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

DOI10.1016/J.IC.2009.02.002zbMATH Open1167.68021OpenAlexW2122475800MaRDI QIDQ2389331FDOQ2389331

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)

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)

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

   Recommendations

• Title not available (Why is that?) 👍 👎
• On uniform amplification of hardness in NP 👍 👎
• A Note on Randomized Polynomial Time 👍 👎
• On circuit lower bounds from derandomization 👍 👎
• Title not available (Why is that?) 👍 👎
• Computing and Combinatorics 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)