Computational Phase Transitions (Simons Institute, 2020)
2020-09-21..2020-09-24
-- online --
[Random Instances and Phase Transitions (Simons Institute, 2016), Information Theory, Learning and Big Data (Simons Institute, 2015), Rigorous Evidence for Information-Computation Trade-offs, Approximate Counting, Markov Chains and Phase Transitions, Meet the Fellows Welcome Event, Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)]
| title | author | length |
|---|---|---|
| Incremental Approximate Message Passing | Ahmed El Alaoui | 01h 31m |
A practical incremental AMP algorithm queries a gradient oracle O(poly(n,1/ε)) times (iterations about O(ε⁻²)), uses orthogonal updates and an Onsager reaction… | ||
| Counting Solutions to Random CNF Formulas | Leslie Ann Goldberg | 41m |
Gives a polynomial-time algorithm that approximates the number of satisfying assignments Z for random k-CNF when k is large and clause density alpha ≤ 2^{r k}… | ||
| Testing Correlation of Unlabeled Random Graphs | Jiaming Xu | 40m |
Derives a sharp statistical threshold: when edge-correlation squared (roughly s^2) exceeds about 2 log n / n (equivalently intersection average degree ≳ log n… | ||
| Local Statistics, Semidefinite Programming, and Community Detection | Jess Banks | 32m |
Proposes a concrete local statistics SDP hierarchy that adds affine constraints built from centered non-backtracking walk constraints (weighted counts) to a… | ||
| Local Statistics, Semidefinite Programming, and Community Detection II | Sidhanth Mohanty | 35m |
Degree-2 local statistics SDP with constraints given by the l-length non-backtracking power of the centered adjacency matrix certifies that the null… | ||
| Equitable Colorings | Afonso Bandeira | 44m |
Random d‑regular graphs have a chromatic lower bound from Hoffman’s spectral bound, and evidence here argues that the bound is essentially tight: an equitable… | ||
| A Positivity-First Approach to Sum-of-Squares Over the Hypercube | Tim Kunisky | 31m |
New method builds pseudoexpectations as actual random symmetric tensors conditioned to satisfy SOS linear constraints, forcing positive semidefiniteness by… | ||
| Optimization of Full-RSB Spherical Spin Glasses | Eliran Subag | 33m |
Proves an explicit polynomial-time algorithm (time ~n^p up to ε-dependent constants) that, under the concave mixture condition equivalent to Parisi support =… | ||
| Thresholds of Descending Algorithms in Inference Problems | Stefano Sarao Mannelli | 35m |
Shows explicit calculation of the critical signal-to-noise value where simple descent methods stop recovering planted structure, giving closed-form thresholds… | ||
| The Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures | Pravesh K. Kothari | 37m |
Polynomial-time algorithm uses the Sum-of-Squares framework to robustly cluster non‑spherical k‑Gaussian mixtures with adversarially corrupted epsilon fraction… | ||
| Pedagogical Talk: Random Optimisation Problems | Amin Coja-Oghlan | 01h 17m |
Examines max‑cut on a random d‑regular graph and shows the usual first‑moment estimate matches the free energy only up to a specific inverse‑temperature… | ||
| Information/Computation Gaps in Heavy-Tailed Statistics | Sam Hopkins | 34m |
Open problem: match the Gaussian high-probability confidence radius r = sqrt(d/n) + sqrt(log(1/δ)/n) for covariance under only bounded moments… | ||
| Correlation Decay for Hard Spheres via Markov Chains | Samantha Petti | 37m |
Defines and analyzes a rejection-free single-center dynamics that picks a random location, adds a disk with probability λ/(1+λ) if it fits, or removes nearby… | ||
| Sampling From the Random Cluster Model at All Temperatures on Random Graphs | Will Perkins | 34m |
For random d‑regular graphs with d ≥ 5 and q at least about d^d, there are polynomial‑time algorithms that approximately count and sample the Potts and… | ||
| The Rank of Sparse Random Matrices | Jane Gao | 36m |
Three random-matrix models (a sparse k-nonzeros per row model, a degree-prescribed simple/flexible models, and a general-field version) have typical rank(A)/n… | ||
| Pedagogical Talk: Failure of Low-Degree Polynomials | Alex Wein | 01h 11m |
Claims that low-degree multivariate polynomials (degree ~log n) both capture common polynomial-time methods and fail where algorithms are conjecturally hard… | ||
| The Overlap Gap Property in Principal Submatrix Recovery | Subhabrata Sen | 39m |
Model: n×n Gaussian matrix with an nρ×nρ planted submatrix of mean λ/n. Information-theoretic boundary shows approximate recovery threshold at λ about 2√(1/ρ ·… | ||
| Free Energy Wells and Overlap Gap Property in Sparse PCA | Ilias Zadik | 34m |
Ilias Zadik, NYU
https://simons.berkeley.edu/talks/free-energy-wells-and-overlap-gap-property-sparse-pca
Computational Phase Transitions | ||
| Reducibility and Statistical-Computational Gaps from Secret Leakage | Guy Bresler | 41m |
Introduces secret leakage planted clique, a generalization where clique locations follow a distribution rho and is conjectured hard whenever two independent… | ||
| Pedagogical Talk: Frameworks for Information-Computation Tradeoffs | Tselil Schramm | 01h 12m |
Shows concrete reductions: if a degree-d sum-of-squares relaxation distinguishes a noise‑robust planted hypothesis, then an explicit degree‑O(d) spectral test… | ||
| Phase Retrieval in High Dimensions: Statistical and Computational Phase Transitions | Florent Krzakala | 39m |
Random Gaussian measurements require weak threshold m/d = β/2 (real 1/2, complex 1) and strong threshold m/d = β (real 1, complex 2); orthogonal ensembles push… | ||
| nothing matches | ||