Source coding by efficient selection of ground states clusters

Abstract

In this letter, we show how the Survey Propagation algorithm can be generalized to include external forcing messages, and used to address selectively an exponential number of glassy ground states. These capabilities can be used to explore efficiently the space of solutions of random NP-complete constraint satisfaction problems, providing a direct experimental evidence of replica symmetry breaking in large-size instances. Finally, a new lossy data compression protocol is introduced, exploiting as a computational resource the clustered nature of the space of addressable states.

4 pages, 4 figures

References in corpus (6)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• A variational description of the ground state structure in random satisfiability problems
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Exact solutions for diluted spin glasses and optimization problems
• Threshold values of Random K-SAT from the cavity method

Cited by in corpus (4)

• Landscape of solutions in constraint satisfaction problems
• Circumspect descent prevails in solving random constraint satisfaction problems
• Survey-propagation decimation through distributed local computations
• Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes