• Statistical physics, optimization and source coding

    • Fulltext


        Click here to view fulltext PDF

      Permanent link:

    • Keywords


      Disordered systems; random combinatorial problems; survey propagation

    • Abstract


      The combinatorial problem of satisfying a given set of constraints that depend on N discrete variables is a fundamental one in optimization and coding theory. Even for instances of randomly generated problems, the question “does there exist an assignment to the variables that satisfies all constraints?” may become extraordinarily difficult to solve in some range of parameters where a glass phase sets in. We shall provide a brief review of the recent advances in the statistical mechanics approach to these satisfiability problems and show how the analytic results have helped to design a new class of message-passing algorithms — the survey propagation (SP) algorithms — that can efficiently solve some combinatorial problems considered intractable. As an application, we discuss how the packing properties of clusters of solutions in randomly generated satisfiability problems can be exploited in the design of simple lossy data compression algorithms.

    • Author Affiliations


      Riccardo Zecchina1

      1. International Centre for Theoretical Physics, Strada Costiera 11, Trieste - I-34100, Italy
    • Dates

  • Pramana – Journal of Physics | News

    • Editorial Note on Continuous Article Publication

      Posted on July 25, 2019

      Click here for Editorial Note on CAP Mode

© 2021-2022 Indian Academy of Sciences, Bengaluru.