Source coding by efficient selection of ground-state clusters
- 18 July 2005
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 72 (1) , 015103
- https://doi.org/10.1103/physreve.72.015103
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.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Instability of one-step replica-symmetry-broken phase in satisfiability problemsJournal of Physics A: General Physics, 2004
- Polynomial iterative algorithms for coloring and analyzing random graphsPhysical Review E, 2003
- Random-satisfiability problem: From an analytic solution to an efficient algorithmPhysical Review E, 2002
- Analytic and Algorithmic Solution of Random Satisfiability ProblemsScience, 2002
- Exact Solutions for Diluted Spin Glasses and Optimization ProblemsPhysical Review Letters, 2001
- On the design of low-density parity-check codes within 0.0045 dB of the Shannon limitIEEE Communications Letters, 2001
- A variational description of the ground state structure in random satisfiability problemsZeitschrift für Physik B Condensed Matter, 2000
- Determining computational complexity from characteristic ‘phase transitions’Nature, 1999
- Near Shannon limit performance of low density paritycheck codesElectronics Letters, 1996
- Critical Behavior in the Satisfiability of Random Boolean ExpressionsScience, 1994