A zero-one law for RP and derandomization of AM if NP is not small
type: Item
instance of: scholarly article
title: A zero-one law for RP and derandomization of AM if NP is not small
zbMATH Open document ID: 1167.68021
author: Russell Impagliazzo
author: Philippe Moser
published in: Information and Computation
publication date: 2009-07-15T00:00:00Z
full work available at URL: PM-Zero-2009.pdf
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5579069
zbMATH Keywords: resource-bounded measure
zbMATH Keywords: derandomization
MaRDI profile type: Publication
OpenAlex ID: W2122475800
cites work: Power from Random Strings
cites work: Q4370034
cites work: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
cites work: In search of an easy witness: Exponential time vs. probabilistic polynomial time.
cites work: Easiness assumptions and hardness tests: Trading time for zero error
cites work: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
cites work: Randomness conservation inequalities; information and independence in mathematical theories
cites work: Derandomizing Arthur-Merlin games under uniform assumptions
cites work: Almost everywhere high nonuniform complexity
cites work: Observations on measure and lowness for \(\Delta_ 2^ p\)
cites work: Q4359463
cites work: The zero-one law holds for BPP
cites work: Baire categories on small complexity classes and meager-comeager laws
cites work: Martingale families and dimension in P
cites work: Q4298260
cites work: Q4231907
DOI: 10.1016/J.IC.2009.02.002
Recommended article: Q2753664
Recommended article: On uniform amplification of hardness in NP
Recommended article: A Note on Randomized Polynomial Time
Recommended article: On circuit lower bounds from derandomization
Recommended article: Q4938630
Recommended article: Computing and Combinatorics
Recommended article: Q5009542
Recommended article: Round Complexity of Common Randomness Generation: The Amortized Setting
Recommended article: Hardness amplification within NP against deterministic algorithms
Recommended article: Relative to a random oracle, NP is not small
description: scientific article