Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Linear Phase Transit ...
Conference paper

Linear Phase Transition in Random Linear Constraint Satisfaction Problems

David Gamarnik (1)
(1) Department of Mathematical Sciences
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2002
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)
Proceedings
DOI
10.46298/dmtcs.3351
License
https://about.hal.science/hal-authorisation-v1
Indicators
664
Views
933
Downloads

Linear Phase Transition in Random Linear Constraint Satisfaction Problems

David Gamarnik (1)
(1) Department of Mathematical Sciences
Abstract
Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints $C$ on $K$ variables is fixed. From a pool of $n$ variables, $K$ variables are chosen uniformly at random and a constraint is chosen from $C$ also uniformly at random. This procedure is repeated $m$ times independently. We are interested in whether the resulting linear programming problem is feasible. We prove that the feasibility property experiences a linear phase transition,when $n→∞$ and $m=cn$ for a constant $c$. Namely, there exists a critical value $c^*$ such that, when $c < c^*$, the problem is feasible or is asymptotically almost feasible, as $n→∞$, but, when $c > c^*$, the "distance" to feasibility is at least a positive constant independent of $n$. Our result is obtained using the combination of a powerful local weak convergence method developed in Aldous [1992, 2000], Aldous and Steele [2003], Steele [2002] and martingale techniques. By exploiting a linear programming duality, our theorem impliesthe following result in the context of sparse random graphs $G(n, cn)$ on $n$ nodes with $cn$ edges, where edges are equipped with randomly generated weights. Let $\mathcal{M}(n,c)$ denote maximum weight matching in $G(n, cn)$. We prove that when $c$ is a constant and $n→∞$, the limit $lim_{n→∞} \mathcal{M}(n,c)/n$, exists, with high probability. We further extend this result to maximum weight b-matchings also in $G(n,cn)$.
Keywords
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
  • Random K-SAT
  • Satisfiability Threshold
  • Linear Programming
  • Sparse Random Graphs
Cited by

Source: OpenCitations

  • An ongoing story

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 517-540

    DOI : 10.1093/acprof:oso/9780198570837.003.0022

  • Weighted enumeration of spanning subgraphs in locally tree‐like graphs

    Authors : Justin Salez ORCID

    Journal reference : Volume 43, 2012, pp. 377-397

    DOI : 10.1002/rsa.20436

  • Satisfiability

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 197-218

    DOI : 10.1093/acprof:oso/9780198570837.003.0010

  • The 1RSB cavity method

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 429-466

    DOI : 10.1093/acprof:oso/9780198570837.003.0019

  • Random K-satisfiability

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 467-492

    DOI : 10.1093/acprof:oso/9780198570837.003.0020

  • The planted matching problem: Phase transitions and exact results

    The Annals of Applied Probability

    Authors : Mehrdad Moharrami ORCID, Cristopher Moore ORCID, Jiaming Xu ORCID

    Journal reference : Volume 31, 2021, pp.

    DOI : 10.1214/20-aap1660

  • Bridges: Inference and the Monte Carlo method

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 267-288

    DOI : 10.1093/acprof:oso/9780198570837.003.0013

  • The assignment problem

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 355-380

    DOI : 10.1093/acprof:oso/9780198570837.003.0016

  • Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

    The Annals of Probability

    Authors : Mohsen Bayati ORCID, David Gamarnik, Prasad Tetali

    Journal reference : Volume 41, 2013, pp.

    DOI : 10.1214/12-aop816

  • Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

    Proceedings of the forty-second ACM symposium on Theory of computing

    Authors : Mohsen Bayati ORCID, David Gamarnik, Prasad Tetali

    Journal reference : Volume , 2010, pp. 105-114

    DOI : 10.1145/1806689.1806706

  • Ising models on random graph

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 381-400

    DOI : 10.1093/acprof:oso/9780198570837.003.0017

  • Belief propogation

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 291-326

    DOI : 10.1093/acprof:oso/9780198570837.003.0014

  • Information, Physics, and Computation

    CERN Document Server (European Organization for Nuclear Research)

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp.

    DOI : 10.1093/acprof:oso/9780198570837.001.0001

  • Symbols and notation

    Information, Physics, and Computation

    Authors :

    Journal reference : Volume , 2009, pp. 541-546

    DOI : 10.1093/acprof:oso/9780198570837.005.0001

  • Factor graphs and graph ensembles

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 173-196

    DOI : 10.1093/acprof:oso/9780198570837.003.0009

  • Linear equations with Boolean variables

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 403-428

    DOI : 10.1093/acprof:oso/9780198570837.003.0018

  • Preface

    Information, Physics, and Computation

    Authors :

    Journal reference : Volume , 2009, pp. v-viii

    DOI : 10.1093/acprof:oso/9780198570837.002.0004

  • A probabilistic toolbox

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 65-90

    DOI : 10.1093/acprof:oso/9780198570837.003.0004

  • Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method

    arXiv (Cornell University)

    Authors : David Gamarnik, Tomasz Nowicki ORCID, Grzegorz Swirszcz

    Journal reference : Volume 28, 2005, pp. 76-106

    DOI : 10.1002/rsa.20072

  • Right-convergence of sparse random graphs

    Probability Theory and Related Fields

    Authors : David Gamarnik

    Journal reference : Volume 160, 2013, pp. 253-278

    DOI : 10.1007/s00440-013-0528-6

  • The random energy model

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 93-106

    DOI : 10.1093/acprof:oso/9780198570837.003.0005

  • Glassy states in coding theory

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 493-516

    DOI : 10.1093/acprof:oso/9780198570837.003.0021

  • Invariant probability measures and dynamics of exponential linear type maps

    Ergodic Theory and Dynamical Systems

    Authors : DAVID GAMARNIK, TOMASZ NOWICKI ORCID, GRZEGORZ ŚWIRSZCZ

    Journal reference : Volume 28, 2008, pp. 1479-1495

    DOI : 10.1017/s014338570700106x

  • Spin glasses

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 241-266

    DOI : 10.1093/acprof:oso/9780198570837.003.0012

  • Introduction to information theory

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 3-22

    DOI : 10.1093/acprof:oso/9780198570837.003.0001

  • Decoding with belief propagation

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 327-354

    DOI : 10.1093/acprof:oso/9780198570837.003.0015

  • The random code ensemble

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 107-130

    DOI : 10.1093/acprof:oso/9780198570837.003.0006

  • Copyright Page

    Information, Physics, and Computation

    Authors :

    Journal reference : Volume , 2009, pp. iv

    DOI : 10.1093/acprof:oso/9780198570837.002.0003

  • Maximum Weight Independent Sets and Matchings in Sparse Random Graphs

    Lecture notes in computer science

    Authors : David Gamarnik, Tomasz Nowicki ORCID, Grzegorz Swirszcz

    Journal reference : Volume , 2004, pp. 357-368

    DOI : 10.1007/978-3-540-27821-4_32

  • Number partitioning

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 131-144

    DOI : 10.1093/acprof:oso/9780198570837.003.0007

  • Statistical physics and probability theory

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 23-46

    DOI : 10.1093/acprof:oso/9780198570837.003.0002

  • Introduction to replica theory

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 145-170

    DOI : 10.1093/acprof:oso/9780198570837.003.0008

  • Introduction to combinatorial optimization

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 47-64

    DOI : 10.1093/acprof:oso/9780198570837.003.0003

  • Counting without sampling: Asymptotics of the log‐partition function for certain statistical physics models

    Random Structures and Algorithms

    Authors : Antar Bandyopadhyay, David Gamarnik

    Journal reference : Volume 33, 2008, pp. 452-479

    DOI : 10.1002/rsa.20236

  • Low-density parity-check codes

    Information, Physics, and Computation

    Authors : Marc Mézard ORCID, Andrea Montanari ORCID

    Journal reference : Volume , 2009, pp. 219-240

    DOI : 10.1093/acprof:oso/9780198570837.003.0011
Preview
Loading PDF preview...