Abstract
We analyze the geometrical structure of clusters of ground states which appear in many frustrated systems over random graphs. Focusing on the regime of connectivities where the number of clusters is exponential in the size of the problems, we identify an appropriate generalization of the survey propagation equations efficiently exploring the geometry. The possibility of selecting different clusters has also computational consequences. As a proof of concept here we show how a well-known physical system can be used to perform nontrivial data compression, for which we introduce a unique compression scheme. Performances are optimized when the number of well-separated clusters is maximal in the underlying physical model.
- Received 24 December 2004
DOI:https://doi.org/10.1103/PhysRevE.72.015103
©2005 American Physical Society