2005 – Statistical mechanics and coding

Many problems of communication theory and computer science can be reformulated in the language of statistical mechanics. Linear error correcting codes, the random K-SAT problem and graph partitionning are examples of problems that can be recast as disordered spin systems (spin glasses). Methods of statistical physics that have proven useful in the theory of spin glasses are the replica and cavity methods. Recently progress has been made in order to find a sound basis for these methods. This has also led to new interpolation techniques.

The aim of this working group will be to go through the replica method, the cavity method, the recent interpolation techniques and also on potentialy useful new forms of correlation inequalities. We will study recent papers that use these to treat problems arising in the communication theory community.

Presentations of papers by interested participants, among the suggested list below (which may evolve), will be done on a weekly basis during an 1h or 1h30.

REPLICA METHOD
Spin Glass Theory and Beyond, by M. Mezard, G. Parisi, M. Virasoro (1987) World Scientific
Statistical Physics of Spin Glasses and Information Processing, by H. Nishimori (2001) Oxford University
The dynamic phase transition for decoding algorithms, S. Franz, M. Leone, A. Montanari, F. Ricci-Tersenghi, Phys. Rev. E 66, 046120 (2002)

CAVITY METHOD
The Bethe spin glass revisited, M. Mezard, G. Parisi, Eur Phys J B 20, 217 (2001)
The cavity method at zero temperature, M. Mezard, G. Parisi, arXiv cond-mat/0207121
Alternative solutions to diluted p-spin models and XORSAT problems, M. Mezard, F. Ricci-Tersenghi, R. Zecchina , J. Stat. Phys 111, 505-533 (2003)
Random K-satisfiability problem: from an analytic solution to an efficient algorithm, M. Mezard, R. Zecchina , Phys Rev E 66, 056126-1 (2002)

INTERPOLATION METHODS AND REPLICA BOUNDS
Quadratic replica coupling in the Sherrington-Kirkpatrick mean field spin glass model, F. Guerra, F. L. Toninelli, J. Math. Phys
Broken replica symmetry bounds in the mean field spin glass model, F. Guerra, Comm. Math. Phys. 233, 1-12 (2003)
Replica bounds for optimisation problems and diluted spin systems, S. Franz, M. Leone, J. Stat. Phys. 111, 535-564 (2003)
Tight bounds for LDPC and LDGM codes under MAP decoding, A. Montanari, cs.IT/0407060

CORRELATION INEQUALITIES
in Phase Transitions and Critical Phenomena vol 1 ed Domb and Green (1972) (London Academic)
Griffiths inequalities for the gaussian spin glass, S. Morita, H. Nishimori, P. Contucci, arXiv cond-mat/0403625
Griffiths-Kelly-Sherman inequalities: a useful tool in the theory of error correcting codes, N. Macris, Trans Inf Theory 2007
Correlation Inequalities on Some Partially Ordered Sets, C.M.Fortuin, P.W.Kasteleyn, J. Ginibre, Commun. Math. Phys vol 22, 89-103 (1971)
also in The Probabilistic Method, N. Alon and J. Spencer (PUP)

APPLICATIONS AND OTHER TOPICS
Survey propagation: an algorithm for stisfiability, A. Braunstein, M. Mezard, R. Zecchina, to appear in Random Structures and Algorithms, cs.CC/0212002 Math Gen 19 (1986) 1605-1620
Application of statistical mechanics to NP complete problems in combinatorial optimisation, Y. Fu, P. W. Anderson, J. Phys. A: Math Gen 19 (1986) 1605-1620
A statistical mechanics approach to large system analysis of CDMA multiuser detectors, T.Tanaka, IEEE Trans Inf Theory, vol 48 (2002)
Statistical mechanics of image restoration and error correcting codes, H. Nishimori, K. Y. Wong, Phys Rev E vol 60 132-144 (1999)
Capacity of noiseless and noisy two dimenesional channels, P.H.Siegel, LANL workshop (2005)
Variational approximations for square lattice models in statistical mechanics, R.J.Baxter, J. Stat. Phys, vol 19 (1978) 461-478