Exact Probing of Glassy States by Survey Propagation
Demian Battaglia, Alfredo Braunstein, Joël Chavas, Riccardo Zecchina · Progress of Theoretical Physics Supplement · 2005
After briefly reviewing the theoretical set up underlying the Survey Propagation (SP) equations, we show how SP can be generalized to include external forcing – external surveys – which allow to address selectively glassy states (which may be exponentially numerous). Taking as working model the random K-SAT problem, we show that the geometrical nature of its different glassy phases can be probed efficiently. A preliminary application of this new algorithm to source coding (lossy data compression) is discussed.