Bypassing Correlation Decay for Matchings with an Application to XORSAT - Archive ouverte HAL Access content directly
Conference Papers Year : 2013

Bypassing Correlation Decay for Matchings with an Application to XORSAT

(1, 2, 3)
1
2
3

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).
Not file

Dates and versions

hal-00917422 , version 1 (11-12-2013)

Identifiers

  • HAL Id : hal-00917422 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More