Playlist: 25 videos

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...

0:43:28

Information-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional Clustering

Cris Moore, Santa Fe Institute
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/cris-moore-2016-05-03
Visit talk page
0:48:13

Spatial Coupling as a Proof Technique

Nicolas Macris, École Polytechnique Fédérale de Lausanne
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/nicolas-macris-2016-05-03
Visit talk page
0:53:10

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

Charilaos Efthymiou, Georgia Institute of Technology
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/charilaos-efthymiou-2016-05-03
Visit talk page
0:46:31

Planted Clique, Sum-of-Squares and Pseudo-Calibration

Ankur Moitra, Massachusetts Institute of Technology
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/ankur-moitra-2016-05-04
Visit talk page
0:44:55

Community Detection with the Non-Backtracking Operator

Marc LeLarge, INRIA
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/marc-lelarge-2016-05-04
Visit talk page
0:46:32

Phase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection)

Fedrico Ricci-Tersenghi, University of Rome La Sapienza
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/federico-ricci-tersenghi-2016-05-04
Visit talk page
0:45:2

Shotgun Assembly of Graphs

Elchanan Mossel, University of Pennsylvania
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/elchanan-mossel-2016-05-05
Visit talk page
0:42:29

Bootstrap Percolation on Random Graphs

Mihyun Kang, Technische Universität Graz, Austria
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/mihyun-kang-2016-05-05
Visit talk page
0:34:38

Contagious Sets in Random Graphs

Daniel Reichman, UC Berkeley
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/daniel-reichman-2016-05-05
Visit talk page
0:47:8

The Large Deviations of the Whitening Process in Random Constraint Satisfaction Problems

Guilhem Semerjian, École Normale Supérieure Paris
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/guilhem-semerjian-2016-05-05
Visit talk page