Jan 24, 2020 12:10pm to 1:00pm
1011 Evans Hall
Happening As Scheduled
Replica Symmetry Breaking for Random Regular NAESAT Ideas from physics have predicted a number of important properties of random constraint satisfaction problems such as the satisfiability threshold and the free energy (the exponential growth rate of the number of solutions). Another prediction is the condensation regime where most of the solutions are contained in a small number of clusters...
Allan Sly, Princeton University