Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
2020-08-19..2020-08-28
-- online --
[Computational Phase Transitions (Simons Institute, 2020), Foundations of Data Science Boot Camp 2018, Geometric Methods in Optimization and Sampling Boot Camp, Robust and High-Dimensional Statistics (Simons Institute workshop, 2018), Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013), Beyond the Boolean Cube 2023]
as the organisers put it
This program aims to advance our understanding of high-dimensional problems by focusing on the interplay between probability, geometry, and computation.
who it's for
theoretical computer scientists, complexity theorists, probabilists and analysts, machine learning researchers, data engineers working on streaming/sketching, statistical physicists
topics
probabilistically checkable proofs (PCP); parallel repetition theorem; long-code gadget and noise tests; Poincaré inequality on the discrete cube; semigroup interpolation and Efron-Stein; Pisier's Gaussian inequality (π/2 constant); distinct counting / Flajolet-Martin sketches; k-wise independent hashing for sketches; linear sketches for sparse recovery and spanning forests; replica method and approximate message passing state evolution
| title | author | length |
|---|---|---|
| Crash Course on Probabilistically Checkable Proofs (PCP): Introduction | Irit Dveer Dinur | 01h 01m |
Crash-course claim: NP languages admit a randomized verifier that reads O(1) proof bits after tossing O(log n) coins, so a polynomial-time reduction maps any… | ||
| Remarks on the Discrete Cube | Ramon van Handel | 01h 00m |
Provides a self-contained proof that Var(f) ≤ Σi E[(Di f)^2] with optimal constant 1 by building an interpolation by continuous-time random walk (independent… | ||
| Remarks on the Discrete Cube | Ramon van Handel | 01h 15m |
Proves the Poincaré inequality on the discrete cube using an explicit semi-group Pt (a product formula with biased Bernoullis), computes D_t Pt = ΔPt and… | ||
| Crash Course on Probabilistically Checkable Proofs (PCP)... | Dana Moshkovitz | 01h 18m |
Gives a constructive weak PCP: map any system of quadratic mod‑2 equations E to a huge Ẽ where each new equation touches only three bits, E satisfiable… | ||
| Crash Course on Probabilistically Checkable Proofs (PCP): Parallel Repetition | Irit Dveer Dinur | 01h 12m |
Parallel repetition takes a projection game and tensorizes it so questions are d-tuples; the basic PCP route uses this to amplify a 1 versus 1−ε gap to 1… | ||
| Remarks on the Discrete Cube | Ramon van Handel | 01h 20m |
Shows the naive Gaussian→cube replacement fails: Talagrand’s L∞ counterexample forces a different formulation. Proves a precise linear→nonlinear principle on… | ||
| Sketching High-Dimensional Data | Jelani Nelson | 01h 10m |
Estimator uses the minimum hashed value of each distinct item (returning 1/X−1), then reduces variance by averaging R independent copies (R ≈ O(1/ε^2)) and… | ||
| Crash Course on Probabilistically Checkable Proofs (PCP): Optimal Inapproximability Results | Dana Moshkovitz | 01h 17m |
Claim: assuming the Unique Games Conjecture, it is NP‑hard to beat the Goemans-Williamson ~0.878 approximation for Max‑Cut. The reduction replaces each… | ||
| Remarks on the Discrete Cube | Ramon van Handel | 01h 21m |
Boolean functions on the discrete cube beat the usual Poincaré bound by two mechanisms: replace L2 by an L1 Poincaré inequality to remove a square, and exploit… | ||
| Sketching High-Dimensional Data | Jelani Nelson | 01h 09m |
Optimal space for one plus epsilon distinct counting is 1/ε^2 log(1/δ)+log n, and both lower and upper bounds are given; deterministic exact algorithms require… | ||
| Statistical Physics and Computation in High Dimension | Florent Krzakala, Lenka Zdeborova | 01h 18m |
Computes typical minimal energy per spin for the random‑field Ising model in the n→∞ limit and shows the average free energy equals the extremum of a replica… | ||
| Recent Progress in High-Dimensional Learning | Ankur Moitra | 01h 03m |
Argues that low‑rank tensor decompositions uniquely recover latent factors under mild linear‑independence conditions and gives an explicit spectral method… | ||
| Sketching High-Dimensional Data | Jelani Nelson | 01h 13m |
Linear sketches estimate norms and heavy hitters with concrete bounds: AMS sketch uses m = Θ(ε^{-2}) rows and O(ε^{-2} log(1/δ)) words to get 1+ε L2 estimates… | ||
| Statistical Physics and Computation in High Dimension | Florent Krzakala, Lenka Zdeborova | 01h 11m |
Lecture contrasts exact limits and practical algorithms: replica and cavity methods give asymptotic mutual information and an information-theoretic recovery… | ||
| Recent Progress in High-Dimensional Learning | Ankur Moitra | 01h 07m |
1D robust estimation uses the median absolute deviation to get O(ε) TV guarantees, but high dimensions face hardness: the Tukey median is robust but NP‑hard… | ||
| Sketching High-Dimensional Data | Jelani Nelson | 01h 10m |
Johnson–Lindenstrauss embedding requires m = O(ε^{-2} log n) and is information-theoretically tight; practical work replaces dense Gaussian maps with faster or… | ||
| Recent Progress in High-Dimensional Learning | Ankur Moitra | 01h 12m |
Shows polynomial‑time algorithms that learn half‑spaces under Massart noise up to error η+ε, first via an improper partitioned classifier and now via a proper… | ||
| Statistical Physics and Computation in High Dimension | Florent Krzakala, Lenka Zdeborova | 01h 03m |
Analyzes teacher-student neural ensembles (committee machines) with analytic replica solution and matching simulations to produce exact learning curves as a… | ||
| Recent Progress in High-Dimensional Learning | Ankur Moitra | 01h 14m |
Provable algorithms reconstruct mixtures of Airy disks from photon samples: for any fixed K a polynomial-time algorithm recovers centers to accuracy ε given… | ||
| Statistical Physics and Computation in High Dimension | Florent Krzakala, Lenka Zdeborova | 01h 04m |
Covers the generalized linear model with five concrete cases: perceptron storage capacity (spherical capacity = 2, binary perceptron conjectured threshold ≈… | ||
| nothing matches | ||