Extractor-Based Approach To Memory-Sample Tradeoffs

on YouTube ↗45m

" summary

The paper proves concrete memory–sample lower bounds by modeling learners as branching programs and using an extractor-based matrix condition (every large submatrix has bias ≤ 2^{-R}). Concretely any learner needs either K·L bits of memory or exp(R) samples; parity needs about N^2/25 bits or exponential samples. Applications: degree‑D multilinear polynomials need ≈N^{D+1} memory or exp samples, sparse linear systems need N·L memory or exp(L) samples, and streaming K‑XOR refutation inherits similar tradeoffs.

AI-written summary · about

" chapters (12)

1. 0:00Introduction
2. 1:06Memory constraints in learning
3. 5:25Parity learning trade-offs
4. 10:14Applications and related work
5. 12:23Extractor-based techniques
6. 14:31Formalizing the learning model
7. 18:23Polynomial and sparse learning
8. 21:02Branching program model
9. 26:33Proof technical details
10. 29:10Refutation of CSPs
11. 34:15Bounds for resilient predicates
12. 40:08Q&A and future directions