Randomness vs Time: Derandomization under a Uniform Assumption

✍ Scribed by Russell Impagliazzo; Avi Wigderson

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 182 KB
• Volume: 63
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.2001.1780

✦ Synopsis

We prove that if BPP ] EXP, then every problem in BPP can be solved deterministically in subexponential time on almost every input (on every sampleable ensemble for infinitely many input sizes). This is the first derandomization result for BPP based on uniform, noncryptographic hardness assumptions. It implies the following gap in the deterministic average-case complexities of problems in BPP: either these complexities are always subexponential or they contain arbitrarily large exponential functions. We use a construction of a small ''pseudorandom'' set of strings from a ''hard function'' in EXP which is identical to that used in the analogous nonuniform results in L.