Algorithmic barriers from phase transitions

Dimitris Achlioptas, Amin Coja-Oghlan

For many random Constraint Satisfaction Problems, by now, we have asymptotically tight estimates of the largest constraint density for which they have solutions. At the same time,…