Derandomization: A Quick Tutorial
summary
Shows a conditional conversion that turns any constant‑round, doubly‑efficient interactive proof into an NP-type deterministic argument with essentially the same verifier time, by replacing each round’s randomness with a targeted PRG (tarPRG) keyed to the current transcript and then enumerating the tiny remaining seed space; as a corollary, for every ε>0 the construction yields a deterministic argument to count satisfying assignments of n‑bit formulas of size 2^{o(n)} in 2^{εn} time, with soundness against 2^{O(n)} adversaries under strong instance‑wise hardness assumptions.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 4:25Fiat-Shamir relation
- 8:07PRGs background
- 13:27Targeted PRGs for proofs
- 27:21Hardness versus randomness
- 35:42Instance-wise hardness
- 41:58Failed PRG approaches
- 46:06Sum-check protocol proof
- 53:24Constant-round protocols collapse
- 57:20Open problems
related talks
10mPseudorandom Generators and Small-Space Derandomization
46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization
55mFoundations 2
01h 08mIncrementally Verifiable Computation for NP from Standard Assumptions
35mVerifiable Luck
57mIndistinguishability Obfuscation from Well-Founded Assumptions
01h 17mCrypto + Meta-complexity 2
01h 15mProofs - Theory