Learning Versus Pseudorandom Generators in Constant Parallel Time
summary
Proves an equivalence: existence of polynomial-stretch PRGs computable in NC0 (collections and single-generator parity-NC0 cases) is exactly captured by average-case hardness of learning under a parameterized sample model. The argument builds explicit reductions using dualization with junta-sparse condition, composes generators via GGM to boost stretch while keeping learning parameters FPT sample complexity, and proposes hardness of random parity decision trees as a concrete candidate; this yields the first characterization linking NC0 PPRGs and learning.
AI-written summary · about
chapters (11)
- 0:00Introduction to the topic
- 2:33Average case learning model
- 4:35Defining PRGs in NC0
- 7:12Constructions and requirements
- 12:20Parameterized learning
- 15:36Characterization results
- 19:39Hardness assumptions
- 25:31Related learning models
- 31:17Dualization technique
- 36:01Connecting hardness and PRGs
- 41:40Meta theorem and conclusion
related talks
25mLearning versus Pseudorandom Generators in Constant Parallel Time
46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization
19mOn the Cryptographic Hardness of Learning One-Hidden Layer Neural Networks
58mObfuscation 2
01h 01mDerandomization: A Quick Tutorial
01h 06mOn the Assumptions Used for Obfuscation
10mPseudorandom Generators and Small-Space Derandomization
57mIndistinguishability Obfuscation from Well-Founded Assumptions