Real Analysis Boot Camp 2013
2013-09-09..2013-09-13
Berkeley, United States
who it's for
computational learning theorists, theoretical computer scientists, complexity theorists, algorithm designers, harmonic analysts, graduate students in theoretical CS
topics
Walsh-Fourier transform on the discrete cube; Markov semigroup and generators on cube; Kushilevitz-Mansour sparse recovery algorithm; decision tree and DNF Fourier bounds; low-degree and L1 polynomial learning; agnostic learning of halfspaces via Hermite; PCP and long-code hardness reductions; gadget reductions for constraint satisfaction; hardness thresholds for Max-3SAT/Max-3-LIN; Bonami inequality and spectral gap estimates
| title | author | length |
|---|---|---|
| Analytic Methods for Supervised Learning I | Adam R. Klivans | 01h 23m |
A concrete claim: decision trees become learnable by finding the largest Fourier coefficients and outputting the sign of a sparse polynomial. The algorithm… | ||
| Introduction to Analysis on the Discrete Cube I | Krzysztof Oleszkiewicz | 01h 32m |
Defines the discrete cube {-1,1}^n with normalized counting measure, L^p norms and Hamming distance, then builds the Walsh functions as an orthonormal basis of… | ||
| Inapproximability of Constraint Satisfaction Problems I | Johan Håstad | 01h 32m |
Claim: it is NP‑hard to beat 7/8 hardness for MAX‑3SAT. Proof outline: reduction from satisfiability via the PCP theorem, then parallel repetition to get a… | ||
| Analytic Methods for Supervised Learning II | Adam R. Klivans | 01h 30m |
Shows that a decision tree with t leaves has L1(f) ≤ t for t‑leaf tree and uses that to get sparse approximations via zeroing small coefficients; states… | ||
| Introduction to Analysis on the Discrete Cube II | Krzysztof Oleszkiewicz | 01h 28m |
Shows that two constructions of the continuous-time random walk on the discrete cube — the lazy discrete-time walk rescaled and independent coordinate Poisson… | ||
| Inapproximability of Constraint Satisfaction Problems II | Johan Håstad | 01h 30m |
Shows NP‑hardness of approximating Max‑3‑LIN/Max‑3‑SAT to within the usual constants (half+ε for 3‑LIN and approaching 7/8+ε for 3‑SAT) by starting from PCP… | ||
| Analytic Methods for Supervised Learning III | Adam R. Klivans | 01h 06m |
Shows an algorithmic pipeline: a projected gradient descent routine approximately solves the polynomial L1 minimization in time poly(n,1/ε,t), which gives an… | ||
| Inapproximability of Constraint Satisfaction Problems III | Johan Håstad | 01h 17m |
Reduction starts from label cover and encodes labels by long codes, analyzes Fourier coefficients and probabilistic labelings to turn a parity test into an… | ||
| Analytic Methods for Supervised Learning IV | Adam R. Klivans | 01h 30m |
Shows that agnostic learning of a single halfspace under the Gaussian reduces to finding a low‑degree polynomial: Hermite/Fourier coefficients give… | ||
| Introduction to Analysis on the Discrete Cube III | Krzysztof Oleszkiewicz | 01h 30m |
Compares concrete semigroups and computes generators explicitly: shift group has generator −d/dx and fails analytic recovery for smooth nonanalytic examples… | ||
| Inapproximability of Constraint Satisfaction Problems IV | Johan Håstad | 01h 25m |
Recap of concrete hardness techniques: starts from label cover with smooth label cover and uses long‑code style tests plus gadget reductions that introduce at… | ||
| Inapproximability of Constraint Satisfaction Problems V | Johan Håstad | 01h 17m |
Argues that standard gadget/LP methods cannot prove NP-hardness for the sparse Hadamard predicate H7 and instead uses a construction that takes… | ||
| Introduction to Analysis on the Discrete Cube IV | Krzysztof Oleszkiewicz | 01h 34m |
Shows the discrete-cube log‑Sobolev inequality holds with constant 2 and derives hypercontractivity bounds that recover Bonami/Kahane moment comparisons for… | ||
| nothing matches | ||