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.

Author: Riccardo Zecchina, International Centre For Theoretical Physics (Ictp)