Learning versus Pseudorandom Generators in Constant Parallel Time
summary
Proves an equivalence: existence of polynomial-stretch pseudorandom generators computable in NC0 is characterized by average-case hardness of weak learning for c-sparse F2 polynomials under distributions samplable by depth-d circuits with FPT sample complexity. Key tools are an NC0 dualization with a junta-sparse condition, a DGM amplification to boost storage while keeping sample complexity FPT, and a candidate hard problem — learning random parity decision trees — whose hardness would yield concrete NC0 PRGs.
AI-written summary · about
chapters (14)
- 0:00Learning vs pseudorandom generators
- 2:55Simple classes vs pseudorandomness in NC0
- 4:18Polynomial-stretch PRGs in NC0
- 6:29PRGs via learning hardness
- 7:35FPT sample complexity approach
- 8:39PRGs and weak learning equivalence
- 10:45Results for sparse polynomials and parity trees
- 11:51Future directions for PRGs
- 12:11Learning parity decision trees
- 13:40Proof techniques in FPT setting
- 19:22Non-self-dualization and junta-sparse
- 21:06Meta theorem for FPT-dualizable classes
- 22:34Main theorem implications
- 23:22Summary and open problems
related talks
50mLearning Versus Pseudorandom Generators in Constant Parallel Time
58mObfuscation 2
53mLPN Based IO Part 2
19mOn the Cryptographic Hardness of Learning One-Hidden Layer Neural Networks
46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization
01h 04mHow to Encrypt a Functionality
57mIndistinguishability Obfuscation from Well-Founded Assumptions
56mContinuous LWE is as Hard as LWE