Random Instances and Phase Transitions

# click the upper-left icon to select videos from the playlist

source: Simons Institute     2016年5月6日
Random Instances and Phase Transitions
May 2 – May 6, 2016
Randomly generated problems have been studied since Erdős and Rényi. They originally attracted interest in computational complexity as a way to study the "average case" complexity of hard combinatorial problems. More recently, however, research has centered on the combinatorial "phase transitions" exhibited by such models. These strongly resemble phase transitions in statistical physics, and have proved to be a useful tool for determining thresholds in computational complexity. A particular area of application has been random constraint satisfaction problems, where physical intuition has led to a deeper understanding and, in some cases, rigorous proofs.
For more information, please visit https://simons.berkeley.edu/workshops/counting2016-3.
These presentations were supported in part by an award from the Simons Foundation.

Counting Solutions to Random Constraint Satisfaction Problems 51:34 Allan Sly, UC Berkeley https://simons.berkeley.edu/talks/all...
A Framework for Imperfectly Observed Networks 46:23
Phase Transitions in Random CSPs 46:26
Analysis of Algorithms on Dense Matrices using Approximate Message Passing 48:51
Recent Advances in Counting Sparse Graphs 48:43
Extremal Cuts of Sparse Random Graphs 48:56
Average-Case Overcomplete Tensor Decomposition 51:33
Phase Transitions in Low-Rank Matrix Estimation 44:35
Learning by Local Entropy Maximization 47:53
Teaching an old code a new trick 45:04
Information-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional Clust 43:28
Spatial Coupling as a Proof Technique 48:12
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model 53:11
Planted Clique, Sum-of-Squares and Pseudo-Calibration 46:30
Community Detection with the Non-Backtracking Operator 44:54
Phase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection) 46:31
Shotgun Assembly of Graphs 45:02
Bootstrap Percolation on Random Graphs 42:29
Contagious Sets in Random Graphs 34:38
The Large Deviations of the Whitening Process in Random Constraint Satisfaction Problems 47:08
On the Chromatic Number of Random Regular Graphs 35:09
The lower tail: Poisson approximation revisited 44:43
Stochastic Integration via Error-Correcting Codes 43:52
Solvable Model of Unsupervised Feature Learning 46:00
Sum of Squares SDP Relaxations on Random Tensors 44:30