Beyond the Boolean Cube 2023
2023-06-26..2023-06-29
Berkeley, United States
who it's for
theoretical computer scientists, complexity theorists, research mathematicians in analysis and combinatorics, quantum algorithms researchers, coding and quantum LDPC researchers, randomized algorithms and sampling researchers, optimization and sum-of-squares practitioners
topics
epsilon-approximate unitary and orthogonal k-designs; high-dimensional expander mixing and reverse hypercontractivity; hypercontractivity on epsilon-product spaces; small-set expansion in short-code and Grassmann graphs; explicit sum-of-squares lower bounds from SS-HDX; product mixing and representation-theoretic bounds on SU(n); parallel discrete sampling via stochastic localization; fractional pseudorandom generators and polarizing random walks; k-fold Forrelation and quantum/classical separations; linearity testing over the biased cube; localization schemes and renormalized Brownian embeddings; representation theory applications in TCS and extremal combinatorics
| title | author | length |
|---|---|---|
| Explicit Orthogonal and Unitary Designs | Ryan O'Donnell | 01h 00m |
Gives a strongly explicit construction of ε‑approximate k‑designs for O(N) and U(N) with N = 2^n, achieving size poly(N^k/ε) (equivalently seed length O(nk +… | ||
| Reverse Hypercotractivity and Improved Sampling in High Dimensional Expanders | Yotam Dikstein | 58m |
Proves that many high-dimensional expanders satisfy reverse hypercontractivity by showing a concrete small-set mixing bound for two noise-like graphs… | ||
| Hypercontractivity Inequality on $\varepsilon$-product Spaces | Siqi Liu | 01h 05m |
Proves a (2,4)-hypercontractivity inequality for general ε-product spaces including spectral high‑dimensional expanders, with a bound that applies to degree‑d… | ||
| Explicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders | Max Hopkins | 01h 04m |
Constructs poly-time constructible XOR-families whose unsatisfiability Sum-of-Squares cannot refute until linear-round SoS lower bounds, matching the Grigoriev… | ||
| Product Mixing, Quantum Separation, and Comfortable Juntas | Noam Lifshitz | 01h 02m |
Proves full product‑mixing for SU_n: if A,B,C have Haar measure > e^{-c n^{1/3}} then Pr[a∈A,b∈B: ab∈C] is within 1.01×μ(C), and this threshold is sharp up to… | ||
| Small-Set Expansion in the 2-Degree Short-Code Graph, the Easier Version | Guy Kindler | 01h 06m |
Proves that the degree-2 short-code graph satisfies small-set expansion for d-global sets by giving a Bonami-style hypercontractive bound: the d-degree part of… | ||
| Unique Games and Expansion | Mitali Bafna | 45m |
Gives concrete algorithms: when low-degree sum-of-squares proofs certify small-set expansion, a degree-2 SoS relaxation plus a conditioning-and-sample rounding… | ||
| Parallel Discrete Sampling via Continuous Walks | Nima Anari | 57m |
Claims first polylogarithmic-time sampling (quasi-RNC or RNC under extra stability) for determinantal point processes, spanning trees and directed Eulerian… | ||
| Strong Bounds for 3-Progressions | Zander Kelley | 01h 04m |
Proves a quantitative improvement showing dense A ⊂ {1..N} with size at least N/C must contain 3-term progressions until C reaches about 2^(log N)^(1/12), and… | ||
| Fractional Pseudorandom Generators | Pooya Hatami | 01h 07m |
Defines a fractional pseudorandom generator that outputs points in the solid cube and shows how a polarizing random walk converts such a fractional PRG into a… | ||
| Noise Stability - Beyond the Boolean cube | Dan Mikulincer | 59m |
Replaces the heat semigroup by a renormalized Brownian motion that martingales the harmonic extension of Boolean functions and embeds the hypercube into Wiener… | ||
| Separating Quantum from Classical with k-fold Forrelation and Friends | Makrand Sinha | 58m |
k-fold Forrelation is easy for quantum machines (about k/2 queries, BQP-complete) but hard for simple classical models: any decision tree or parity decision… | ||
| It ain't over till it's over | Pei Wu | 57m |
Balanced Boolean functions with variance Ω(1) and max influence τ remain nonconstant with overwhelming probability after fixing all but a \tilde{Ω}((log… | ||
| Sparsifying Sums of Norms | Yang Liu | 01h 03m |
For N(x)=Σi Ni(x) there exist nonnegative weights w with only O(ε^{-2} n log(n/ε) (log n)^{2.5}) nonzeros and |N(x)−Σi wiNi(x)| ≤ εN(x) for all x, found by… | ||
| Linearity Testing over the Biased Cube | Amey Bhangale | 01h 00m |
Gives a 4-query p-biased test (queries marginally p-distributed) that works for p in (1/2,2/3), with perfect completeness and soundness 1/2; constructs a… | ||
| Localization Schemes | Yuansi Chen | 01h 00m |
Introduces a framework that turns mixing-time proofs into two tasks: pick a localization scheme and prove approximate conservation of variance or entropy along… | ||
| On Perfectly Friendly Bisections of Random Graphs | Mehtaab Sawhney | 57m |
Proves a sharp threshold: there is a constant γ so G ~ G(n,1/2) with high probability has an equipartition where every vertex has at least (γ−ε)√n more… | ||
| Representation Theory in TCS and Extremal Combinatorics | Nathan Lindzey | 51m |
Introduces association schemes as the framework for exporting Fourier methods beyond the Boolean cube and uses group representation concretely to analyze the… | ||
| nothing matches | ||