New Approaches to Heuristic Pac-learning vs. PRFs
summary
Proves that, under the nonexistence of PRFs, Naor–Reingold’s pseudorandom synthesizer reduction yields a concrete algorithmic consequence: most polynomial-size circuits become weak PAC-learnable over most polynomial-time samplable distributions, and the argument scales down to NC (log-depth) families giving weak learners for NC-representable concepts. Construction encodes a heuristic learning problem as a synthesizer, uses the NR99 PRS→PRF pipeline to convert a PRF distinguisher into a predictor, overcomes hybrid-correlation obstacles in sampling, and outputs an explicit weak learner (boosting to strong left as standard but not fully executed).
AI-written summary · about
chapters (19)
- 0:00Introduction
- 4:30equivalences
- 6:30oneway function
- 15:00parallel circuits
- 17:00robustness
- 17:45Context
- 19:25Merge
- 20:10Weak PRFs
- 20:55Heuristic Constructions
- 25:10Whats a pseudonym synthesizer
- 27:10Whats a student synthesizer
- 29:05Ringgold
- 34:00Technical Obstacles
- 34:45Encoding a synthesizer
- 36:25Block Matrix Interpretation
- 36:56Hybrids
- 40:16Hypothesis
- 41:26CRK vs NW
- 42:45Open Problems
related talks
57mTowards P≠NP from Extended Frege Lower Bounds
21mA Functional Approach to Synthesizing Routable Programmable Accelerators for Neural(…)
47mNatural Proofs in Algebraic Circuit Complexity
01h 02mTheory and Control
01h 30mInapproximability of Constraint Satisfaction Problems II
22mNew Lower Bounds and Derandomization for ACC, and a...
06mStatic Delayed Sampling for Probabilistic Programming Languages
25mRecursive Program Synthesis using Paramorphisms