From clustering to algorithms

In this talk we firstly provide a rigorous probabilistic proof of the clustering phenomenon taking place in the space of solution of random combinatorial problems. Secondly we will discuss a generalization of the survey propagation equations efficiently exploring the clustered geometry. Finally, we discuss the computational consequences of the possibility of finding single clusters by describing a \"physical\" lossy compression scheme. Performance are optimized when the number of well separated clusters is maximal in the underlying physical model.