Skip to Main content Skip to Navigation
Conference papers

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, 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).
Document type :
Conference papers
Complete list of metadatas
Contributor : Marc Lelarge <>
Submitted on : Wednesday, December 11, 2013 - 6:42:17 PM
Last modification on : Tuesday, September 22, 2020 - 3:46:57 AM


  • HAL Id : hal-00917422, version 1


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



Record views