Pseudorandom Generators for Unbounded-Width Permutation Branching Programs
summary
Presents an explicit INW-style generator that has seed length O(log n log(1/ε) + log n log log n) for permutation branching programs of arbitrary width, proved by derandomized squaring using auxiliary expanders with λ = O(ε/log n) and the INW concatenation trick; shows a random function with seed o(n) fails to be a PRG with high probability by embedding permutation testers, and proves a matching lower bound Ω(log n · log(1/ε)) for any ε-PRG. The constructed generator succeeds; random functions provably do not.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:15Pseudorandom Generators
- 2:08Ordered Branching Program Evaluation
- 2:46Pseudorandomness for Branching Programs
- 3:42Permutation Branching Programs
- 6:58Powering the Execution Graph
- 8:18Graphs Induced by Generators
- 12:13Derandomized Square of (RV05)
- 13:45Unit Circle Approximation
- 18:46A Random Function is not a PRG
- 20:47Failure Of Probabilistic Method
- 22:54Lower Bound II
- 24:44Conclusion
- 25:29Open Questions and Further Directions
related talks
55mFoundations 2
10mPseudorandom Generators and Small-Space Derandomization
44mLPN Based IO Part 1
53mFoundations 1
46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization
57mIndistinguishability Obfuscation from Well-Founded Assumptions
01h 01mDerandomization: A Quick Tutorial
37mSuccinct Randomized Encodings from Laconic Function Evaluation, Faster and Simpler