Bypassing Correlation Decay for Matchings with an Application to XORSAT

Marc Lelarge 1, 2, 3
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : Many combinatorial optimization problems on sparse graphs do not exhibit the correlation decay property. In such cases, the cavity method remains a sophisticated heuristic with no rigorous proof. In this paper, we consider the maximum matching problem which is one of the simplest such example. We show that monotonicity properties of the problem allows us to define solutions for the cavity equations. More importantly, we are able to identify the 'right' solution of these equations and then to compute the asymptotics for the size of a maximum matching. The results for finite graphs are self-contained. We give references to recent extensions making use of the notion of local weak convergence for graphs and the theory of unimodular networks. As an application, we consider the random XORSAT problem which according to the physics literature has a 'one-step replica symmetry breaking' (1RSB) glass phase. We derive new bounds on the satisfiability threshold valid for general graphs (and conjectured to be tight).
Type de document :
Communication dans un congrès
IEEE Information Theory Workshop, Sep 2013, Seville, Spain. 2013
Liste complète des métadonnées

https://hal.inria.fr/hal-00917422
Contributeur : Marc Lelarge <>
Soumis le : mercredi 11 décembre 2013 - 18:42:17
Dernière modification le : jeudi 11 janvier 2018 - 06:25:34

Identifiants

  • HAL Id : hal-00917422, version 1

Collections

Citation

Marc Lelarge. Bypassing Correlation Decay for Matchings with an Application to XORSAT. IEEE Information Theory Workshop, Sep 2013, Seville, Spain. 2013. 〈hal-00917422〉

Partager

Métriques

Consultations de la notice

146