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:35:9

On the Chromatic Number of Random Regular Graphs

Samuel Hetterich, Goethe University Frankfurt
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/samuel-hetterich-2016-05-05
Visit talk page
0:44:44

The Lower Tail: Poisson Approximation Revisited

Lutz Warnke, University of Cambridge
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/lutz-warnke-2016-05-05
Visit talk page
0:43:53

Stochastic Integration via Error-Correcting Codes

Dimitris Achlioptas, UC Santa Cruz
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/dimitris-achlioptas-2016-05-06
Visit talk page
0:46:0

Solvable Model of Unsupervised Feature Learning

Lenka Zdeborova, CNRS and CEA Saclay
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/lenka-zdeborova-2016-05-06
Visit talk page
0:44:30

Sum of Squares SDP Relaxations on Random Tensors

Prasad Raghavendra, UC Berkeley
Random Instances and Phase Transitions
https://simons.berkeley.edu/talks/prasad-raghavendra-2016-05-06
Visit talk page