A new general derandomization method

DOI10.1145/273865.273933zbMATH Open0903.68089OpenAlexW2025819235MaRDI QIDQ3841044FDOQ3841044

Andrea Clementi, Alexander E. Andreev, José Rolim

Publication date: 5 January 1999

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1998-45/

zbMATH Keywords

quick hitting set generatorsquick pseudorandom generators

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Cited In (16)

• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Title not available (Why is that?)
• Pseudo-random generators for all hardnesses
• Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
• Paradigms for Unconditional Pseudorandom Generators
• A Generalization of Peres’s Algorithm for Generating Random Bits From Loaded Dice
• Title not available (Why is that?)
• Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?
• Randomness vs time: Derandomization under a uniform assumption
• Simplified Derandomization of BPP Using a Hitting Set Generator
• Reconstructive dispersers and hitting set generators
• A Fast Derandomization Scheme and Its Applications
• Title not available (Why is that?)
• Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?
• Small-bias is not enough to hit read-once CNF
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory

This page was built for publication: A new general derandomization method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3841044)