title: Source coding by efficient selection of ground-state clusters.
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.
authors.affiliation: SISSA, Via Beirut 9, I-34100 Trieste, Italy.
authors.forename: Demian
authors.initials: D
authors.lastname: Battaglia
authors.forename: Alfredo
authors.initials: A
authors.lastname: Braunstein
authors.forename: Joël
authors.initials: J
authors.lastname: Chavas
authors.forename: Riccardo
authors.initials: R
authors.lastname: Zecchina