Random Instances and Phase Transitions (Simons Institute, 2016)
2016-05-02..2016-05-06
Berkeley, United States
[Computational Phase Transitions (Simons Institute, 2020), Approximate Counting, Markov Chains and Phase Transitions, Rigorous Evidence for Information-Computation Trade-offs, Algorithmic Advances for Statistical Inference with Combinatorial Structure, Information Theory, Learning and Big Data (Simons Institute, 2015), Randomized Numerical Linear Algebra and Applications 2018]
| title | author | length |
|---|---|---|
| Counting Solutions to Random Constraint Satisfaction Problems | Allan Sly | 52m |
Proves the free‑energy limit for a D‑regular NAE‑SAT model (binary, locally homogeneous) and shows it matches the one‑step replica‑symmetry‑breaking… | ||
| A Framework for Imperfectly Observed Networks | David Aldous | 46m |
Model assumes a finite edge-weighted graph where each potential edge generates a Poisson interaction process with rate equal to its weight, and the data is the… | ||
| Phase Transitions in Random CSPs | Nike Sun | 46m |
Random regular k-SAT on a bipartite factor graph gets a rigorous 1RSB free-energy: for large K the limit of (1/N) log Z exists in probability and matches an… | ||
| Analysis of Algorithms on Dense Matrices using Approximate Message Passing | Andrea Montanari | 49m |
A specific algorithmic claim: iterating a centered, rescaled dense random matrix with a component-wise nonlinearity plus an explicit Onsager reaction term… | ||
| Recent Advances in Counting Sparse Graphs | Sourav Chatterjee | 49m |
Asks whether upper tails for subgraph counts follow a variational entropy formula and shows a sufficient condition: the gradient of the counting polynomial… | ||
| Extremal Cuts of Sparse Random Graphs | Amir Dembo | 49m |
Claim: for sparse random graphs (Erdos–Rényi or random regular) the extremal cuts have leading value nγ/4 and the first nontrivial correction is ± const · n√γ… | ||
| Average-Case Overcomplete Tensor Decomposition | David Steurer | 52m |
Presents a concrete algorithmic path: use sum-of-squares pseudo-distributions to “lift third to sixth moments”, enforce a spectral-norm/maximum-entropy… | ||
| Phase Transitions in Low-Rank Matrix Estimation | Florent Krzakala | 45m |
Florent Krzakala, École Normale Supérieure Paris
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/florent-krzakala-2016-05-03 | ||
| Learning by Local Entropy Maximization | Riccardo Zecchina | 48m |
Claim: random binary perceptrons hide rare local entropy maxima—exponentially dense clusters of solutions that standard replica analyses miss. Tools… | ||
| Teaching an old code a new trick | Rüdiger Urbanke | 45m |
Reed–Muller codes provably reach Shannon capacity on the binary erasure channel for every rate by combining three concrete facts: two-transitive symmetry of… | ||
| Information-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional Clust | Cris Moore | 43m |
Uses the second moment method and small-subgraph conditioning to bound when planted structure is statistically detectable versus a null Erdős–Rényi graph… | ||
| Spatial Coupling as a Proof Technique | Nicolas Macris | 48m |
Proves that for regular LDPC ensembles with even check degree and large fixed degrees the asymptotic conditional entropy equals the supremum of a replica… | ||
| Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model | Charilaos Efthymiou | 53m |
Charilaos Efthymiou, Georgia Institute of Technology
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/charilaos-efthymiou-2016-05-03 | ||
| Planted Clique, Sum-of-Squares and Pseudo-Calibration | Ankur Moitra | 47m |
Shows that level-D Sum-of-Squares cannot rule out planted cliques much below √n: the integrality gap is ≥ n^{1/2 - O(√D / log n)} for D = o(log n), so any SOS… | ||
| Community Detection with the Non-Backtracking Operator | Marc Lelarge | 45m |
Shows that the non-backtracking operator (the edge-to-edge B matrix) produces an eigenvalue outside the bulk for sparse random graphs when the signal-to-noise… | ||
| Phase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection) | Fedrico Ricci-Tersenghi | 47m |
A semidefinite programming approach produces a fast, robust algorithm for community detection by optimizing a relaxed trace objective over low‑rank correlation… | ||
| Shotgun Assembly of Graphs | Elchanan Mossel | 45m |
Elchanan Mossel, University of Pennsylvania
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/elchanan-mossel-2016-05-05 | ||
| Bootstrap Percolation on Random Graphs | Mihyun Kang | 42m |
Proves an explicit formula for the critical initial size a_c for r-threshold bootstrap percolation on G(n,p) when n^{-1} << p << n^{-1/r}, shows the critical… | ||
| Contagious Sets in Random Graphs | Daniel Reichman | 35m |
Daniel Reichman, UC Berkeley
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/daniel-reichman-2016-05-05 | ||
| The Large Deviations of the Whitening Process in Random Constraint Satisfaction Problems | Guilhem Semerjian | 47m |
Guilhem Semerjian, École Normale Supérieure Paris
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/guilhem-semerjian-2016-05-05 | ||
| On the Chromatic Number of Random Regular Graphs | Samuel Hetterich | 35m |
Determines the chromatic number of random d‑regular graphs for almost all d by pinning explicit upper and lower bounds and showing an explicit integer D_k that… | ||
| The lower tail: Poisson approximation revisited | Lutz Warnke | 45m |
Proves sharp lower-tail asymptotics for subgraph counts in G(n,p): when each indicator probability max(pi) -> 0 and dependency measure Δ -> 0 and ε^2·E[X_H] ->… | ||
| Stochastic Integration via Error-Correcting Codes | Dimitris Achlioptas | 44m |
Proposes estimating a partition function by taking medians of maxima over random subsets defined as solutions to linear parity systems, using a generator… | ||
| Solvable Model of Unsupervised Feature Learning | Lenka Zdeborova | 46m |
Defines a planted sparse dictionary matrix factorization (Gaussian noise, iid dictionary, sparse X) and computes the information‑theoretic MMSE via the… | ||
| Sum of Squares SDP Relaxations on Random Tensors | Prasad Raghavendra | 45m |
Proves a concrete runtime vs. guarantee tradeoff: a degree-d Sum-of-Squares proof (computed in time n^{O(d)}) certifies strictly better upper bounds on the… | ||
| nothing matches | ||