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:51:34

Counting Solutions to Random Constraint Satisfaction Problems

Allan Sly, UC Berkeley
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/allan-sly-2016-05-02
Visit talk page
0:46:24

A Framework for Imperfectly Observed Networks

David Aldous, UC Berkeley
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/david-aldous-2016-05-02
Visit talk page
0:46:26

Phase Transitions in Random CSPs

Nike Sun, UC Berkeley
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/nike-sun-2016-05-02
Visit talk page
0:48:52

Analysis of Algorithms on Dense Matrices using Approximate Message Passing

Andrea Montanari, Stanford University
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/andrea-montanari-2016-05-02
Visit talk page
0:48:44

Recent Advances in Counting Sparse Graphs

Sourav Chatterjee, Stanford University
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/sourav-chatterjee-2016-05-02
Visit talk page
0:48:56

Extremal Cuts of Sparse Random Graphs

Amir Dembo, Stanford University
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/amir-dembo-2016-05-02
Visit talk page
0:51:33

Average-Case Overcomplete Tensor Decomposition

David Steurer, Cornell University
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/david-steurer-2016-05-03
Visit talk page
0:44:35

Phase Transitions in Low-Rank Matrix Estimation

Florent Krzakala, École Normale Supérieure Paris
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/florent-krzakala-2016-05-03
Visit talk page
0:47:53

Learning by Local Entropy Maximization

Riccardo Zecchina, Politecnico di Torino
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/riccardo-zecchina-2016-05-03
Visit talk page
0:45:4

Teaching an Old Code a New Trick

Rüdiger Urbanke, École Polytechnique Fédérale de Lausanne
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/rudiger-urbanke-2016-05-03
Visit talk page