Randomness vs time: Derandomization under a uniform assumption

DOI10.1006/jcss.2001.1780zbMath1052.68034OpenAlexW2062855793MaRDI QIDQ1604214

Russell Impagliazzo, Avi Wigderson

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2001.1780

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25)

Related Items

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Circuit lower bounds from learning-theoretic approaches, The size of SPP, Two Comments on Targeted Canonical Derandomizers, Worst-Case to Average-Case Reductions for Subclasses of P, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), Paradigms for Unconditional Pseudorandom Generators, Unnamed Item, A zero-one SUBEXP-dimension law for BPP, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Unnamed Item, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, On uniformity and circuit lower bounds, Limits on the Computational Power of Random Strings, Pseudorandom generators without the XOR lemma, Natural Proofs versus Derandomization, Unions of Disjoint NP-Complete Sets, Efficient learning algorithms yield circuit lower bounds, Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification, Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification, In a World of P=BPP, Randomness and Intractability in Kolmogorov Complexity, Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Turing machines that take advice
• Pseudorandom bits for constant depth circuits
• One way functions and pseudorandom generators
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• Oracles and queries that are sufficient for exact learning
• Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
• Hardness and hierarchy theorems for probabilistic quasi-polynomial time
• On Yao’s XOR-Lemma
• Extractors and pseudo-random generators with optimal seed length
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• PP is as Hard as the Polynomial-Time Hierarchy
• Average Case Complete Problems
• A new general derandomization method
• A Pseudorandom Generator from any One-way Function
• Weak Random Sources, Hitting Sets, and BPP Simulations
• On the Existence of Pseudorandom Generators
• Natural proofs