Boolean Hardness to Randomization
summary
Shows a blueprint that converts a worst‑case hard Boolean function into a pseudorandom generator g so that any small circuit that distinguishes g’s outputs from uniform yields a smaller circuit solving the original function. Key tools are worst‑case→average‑case amplification via locally decodable error‑correcting code, list decoding, and extractor constructions; quantitative consequences include derandomizing Promise‑BPP to deterministic time 2^{n^ε} from mild circuit lower bounds and full P=Promise‑BPP from exponential lower bounds.
AI-written summary · about
chapters (11)
- 0:00Introduction to randomness
- 3:50Randomized algorithms
- 7:18Meta-algorithmic connection
- 10:48Derandomization paradigms
- 14:11Circuit approximation
- 19:14Hardness-to-randomness
- 24:03Constructive frameworks
- 32:20Randomness extractors
- 39:20Error-correcting codes
- 50:51Decoding and entropy
- 59:36Complexity results
related talks
01h 03mBeyond Boolean Circuits in Garbled Circuits
39mBroadcasting on Directed Acyclic Graphs
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
57mCoding for Interactive Communication
23mTowards General and Tight Hardness Results for Graph Problems
33mGeometry of Secure Computation
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
18mEqual Opportunity: A Correctness Condition for Ordered Consensus