Analysis and TCS Boot Camp 2023
2023-06-05..2023-06-09
Berkeley, United States
[Neo-Classical Methods in Discrete Analysis 2013, Beyond the Boolean Cube 2023, Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020), Fine-Grained Complexity and Algorithm Design Boot Camp 2015, Bridging Continuous and Discrete Optimization Boot Camp 2017, Functional Inequalities in Discrete Spaces with Applications 2013]
as the organisers put it
The boot camp is intended to acquaint program participants with the key themes of the program. It will consist of five days of tutorial presentations.
who it's for
theoretical computer scientists, complexity theorists, combinatorics researchers, graduate students in TCS, coding theorists, probabilists, mathematicians working in spectral theory
topics
Fourier analysis on Boolean cube; random restrictions and KKL; hypercontractivity and noise operator; high-dimensional expanders; up and down operators; spectral independence and log-concave polynomials; tools from stochastic calculus; PCP and label-cover hardness; small-set expansion in p-biased cube; Grassmann graph expansion theorem; decision tree Fourier bounds
| title | author | length |
|---|---|---|
| Introduction to Analysis of Boolean Functions 1 | Hamed Hatami | 01h 00m |
Develops Fourier analysis on finite abelian groups and the Boolean cube, proving that characters are roots of unity, that a non‑principal character sums to… | ||
| Introduction to Analysis of Boolean Functions 2 | Hamed Hatami | 01h 02m |
Defines convolution and proves its Fourier transform becomes a pointwise product so averaging operators (Hamming balls, measures) translate cleanly into… | ||
| Random Restrictions and Fourier Concentration 1 | Esty Kelman | 01h 00m |
Proves the KKL lower bound that a balanced Boolean function has some variable influence at least constant times log n / n, using random restrictions and… | ||
| Random Restrictions and Fourier Concentration 2 | Esty Kelman | 56m |
Correlation inequality uses hypercontractivity (L4 bound ~3^d) to bound E[f g] for Boolean f and degree-d real g and deduces KKL and Friedgut-style… | ||
| High-Dimensional Expanders 1 | Irit Dveer Dinur | 01h 01m |
Defines a d-dimensional lambda link expander: every link (neighborhood of a face) has 1-skeleton with spectral gap ≤ lambda, and shows this local property… | ||
| High-Dimensional Expanders 2 | Irit Dveer Dinur | 01h 03m |
Proves a concrete local‑to‑global claim: link expander ⇒ random‑walk expander by rewriting the upper walk as an expectation over links, bounding Mi+⟨f,f⟩ by… | ||
| Introduction 3 - Hyper-contractivity | Noam Lifshitz | 01h 01m |
Defines the noise operator on the Boolean cube (resample each bit independently with probability 1−ε), proves Tε acts on Fourier characters by ε^{|S|} and that… | ||
| Applications in Extremal Combinatorics 1 | Noam Lifshitz | 01h 01m |
Survey of how junta-style decompositions and Fourier-type bases give concrete extremal bounds: Friedgut and Kindler–Safra analogues extend to families, S_n and… | ||
| High-Dimensional Expanders 3 | Max Hopkins | 01h 02m |
Constructs a concrete levelwise decomposition of functions on a k‑dimensional simplicial complex by lifting kernels of the down operator and proves uniqueness… | ||
| High-Dimensional Expanders 4 | Max Hopkins | 01h 07m |
Claim: global hypercontractivity and small-set expansion for epsilon-global functions on the p-biased cube extend to certain high-dimensional expanders by… | ||
| PCPs and Global Hyper-contractivity 1 | Dor Minzer | 50m |
Label-cover is formalized with bipartite alphabets and projection constraints and is NP-hard to distinguish full satisfiability from ≤1−ε for constant alphabet… | ||
| PCPs and Global Hyper-contractivity 3 | Dor Minzer | 01h 00m |
States the Grassmann expansion theorem: any r‑ε global subset of the Grassmann graph has edge expansion tending to 1. Proof framework builds the degree (junta)… | ||
| Log-concave Polynomials and Spectral Independence 1 | Kuikui Liu | 01h 05m |
Defines spectral independence as the largest eigenvalue of a conditional influence matrix and proves bounded η for all conditionals yields a spectral gap ≳… | ||
| Log-concave Polynomials and Spectral Independence 2 | Kuikui Liu | 01h 00m |
Shows that log-concavity of g_mu and explicit zero-free region around 1 each imply spectral independence by translating marginals and pairwise influences into… | ||
| Tools from Stochastic Calculus 1 | Ronen Eldan | 58m |
Defines a multilinear extension on [-1,1]^n and builds a coordinate-revealing random walk X0→Xn: choose a random permutation Ki and iid ±1 epsilons, set… | ||
| Tools from Stochastic Calculus 2 | Ronen Eldan | 01h 08m |
Constructs a continuous bit-sampling martingale from Brownian stopping times whose coordinates are iid copies and whose one-step jump probability is… | ||
| Tools from Stochastic Calculus 3 | Ronen Eldan | 01h 12m |
Main lemma shows the stopping time τ when ∥∇f(x_t)∥ exceeds a fixed constant has probability ≥ 1/200 when Var(f) ≥ 1/100, via equality between expected… | ||
| Log-concave Polynomials and Spectral Independence 3 | Kuikui Liu | 56m |
Shows that spectral independence of all conditionals gives a concrete mixing bound: with ζ-SI the Glauber spectral gap is at least 1/n^{1+ζ}; adding a global… | ||
| PCPs and Global Hyper-Contractivity 2 | Dor Minzer | 01h 04m |
Starts by showing a long-code with a simple noise tester (one coordinate kept with probability 1−ε) that is complete but far too large to be useful, contrasts… | ||
| Applications in Extremal Combinatorics 2 | Noam Lifshitz | 01h 03m |
Shows hypercontractivity for global functions combined with a decomposition into global parts to convert level‑d inequalities into exponentially stronger… | ||
| PCPs and Global Hyper-contractivity 1 | Dor Minzer | 59m |
Explains that the PCP theorem is recast as a small-alphabet label cover hardness (constant k, gap 1 vs 1−ε), develops the Unique Games Conjecture as the… | ||
| nothing matches | ||