Pseudorandom Generators and Small-Space Derandomization
summary
Construction shows a concrete PRG that maps 2-bit seed -> 3-bit output: (x,y,x xor y) and therefore is pairwise independent and fools depth-2 decision trees. More generally, explicit PRGs are given for read-once bounded-depth circuits, bounded-depth threshold circuits, and certain branching programs. Best unconditional derandomization currently converts BPSPACE(S) to deterministic space about S^{3/2}/sqrt(log S), and quasilinear-time, log-space randomized algorithms become log-space deterministic but only typically correct in the current results.
AI-written summary · about
chapters (5)
related talks
01h 01mDerandomization: A Quick Tutorial
46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization
26mPseudorandom Generators for Unbounded-Width Permutation Branching Programs
55mFoundations 2
53mFoundations 1
44mLPN Based IO Part 1
01h 02mTree PCPs
23mSmall-Box Cryptography