@incollection{statphys23_0561,
	title = {Constraint Satisfaction Problems: From Physics to Algorithms},
	address = {Genova, Italy},
	author = {D. Achlioptas and F. Ricci-Tersenghi},
	booktitle = {Abstract Book of the XXIII IUPAP International Conference on Statistical Physics},
	editor = {Luciano Pietronero and Vittorio Loreto and Stefano Zapperi},
	month = {9-13 July},
	url = {http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=561},
	year = {2007},
	biburl = {http://www.bibsonomy.org/bibtex/2fd2b05f0a8397aa5ddaa6647fbfdf68c/statphys23},
	abstract = {For a number of random constraint satisfaction problems (CSPs) all provably efficient algorithms stop finding solutions much before those cease to exist. To understand the origin of this phenomenon we study the evolution of the structure of the space of solutions in random CSPs as constraints are added. In particular, we will survey both what physicists hypothesize happens in this evolution, and what has been rigorously proven so far. We will see that the rigorous results are in agreement with the physics predictions and elucidate Survey Propagation, an extremely successful heuristic proposed by physicists for random CSPs.},
	keywords = {algorithms clustering glasses phase propagation spin statphys23 survey topic-2 transitions }
}