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

DOI10.1016/J.IC.2009.02.002MaRDI QIDQ2389331zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

derandomizationresource-bounded measure

Mathematics Subject Classification ID

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

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

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

Cited in

(2)

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

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)