### General

organizer | Nicolas Macris |

office | INR 134 |

phone | 693 81 14 |

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*