2005 – Statistical mechanics and coding

 

General

   
organizer Nicolas Macris
office INR 134
phone 693 81 14
email nicolas.macris@epfl.ch 
schedule mondays from 11h00 until 12h30
location room INR 113 

Topic

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.

Tentative schedule

 

speaker date topic
     
Nicolas Macris Nov 11 Intro: stat mech formulation of coding, K-sat, graph partitionning
Nicolas Macris Nov 18 The SK model: introduction to replica and cavity methods
Nicolas Macris Nov 25 Replica and cavity methods continuation
Vishwambhar Rathi Nov 29 Application of statistical mechanics to NP complete problems in combinatorial optimisation
Daniella Tuninetti & Olivier Leveque Dec 6 Quadratic replica coupling in the Sherrington-Kirkpatrick mean field spin glass model
Daniela Tuninetti & Olivier Leveque Dec 13 Guerra’s interpolation method continuation
Abdel Amraoui & Olivier Dousse Dec 20 The cavity method at zero temperature
Abdel Amraoui & Olivier Dousse Jan 10 The cavity method at zero temperature continuation
Abdel Amraoui & Olivier Dousse Jan 17 The cavity method at zero temperature continuation
Shrinivas Kudekar Jan 24 Alternative solutions to diluted p-spin models and XORSAT problems
Shrinivas Kudekar Jan 31 Alternative solutions to diluted p-spin models and XORSAT problems continuation
Shrinivas Kudekar Feb 7 Continuation on XORSAT notion of complexity and relationship with ground state energy
Cyril Measson Feb 14 Continuation on XORSAT Wormald method and comparison with cavity method
Cyril Measson Feb 21 Continuation on XORSAT
Cyril Measson Feb 28 End of XORSAT
Break March 7
Ruediger Urbanke March 14 Tight bounds for LDPC codes under MAP decoding Concentration
Ruediger Urbanke march 14 Tight bounds for LDPC codes under MAP decoding Interpolation
Easter holiday March 28
Satish Korada April 4 A statistical mechanics approach to large system analysis of CDMA multiuser detectors
Satish Korada April 11 A statistical mechanics approach to large system analysis of CDMA multiuser detectors
Ruediger Urbanke April 18 Tight bounds for LDPC and LDGM codes under MAP decoding Interpolation
Sanket Dusad & Shrinivas Kudekar April 25 Random K-satisfiability problem from an analytic solution to an efficient algorithm
Sanket Dusad & Shrinivas Kudekar May 2 Survey propapgation an algorithm for satisfiability
Nicolas Macris May 9 Griffiths inequalities for the gaussian spin glass
holiday May 16
Nicolas Macris May 23 GKS inequalities a useful tool for error correcting codes
Vishwambhar Rathi May 30 The four function theorem and Fortuin-Kasteleyn-Ginibre inequality
Henry Pfister June 6 Constrained Codes and Statistical Physics
Nicolas Macris June 13 FKG inequality continuation

 

Reading material

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