Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
From MaRDI portal
Publication:5891427
DOI10.1145/1806689.1806706zbMath1293.05350arXiv0912.2444WikidataQ106094403 ScholiaQ106094403MaRDI QIDQ5891427
David Gamarnik, Mohsen Bayati, Prasad Tetali
Publication date: 13 August 2014
Published in: The Annals of Probability, Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0912.2444
68Q25: Analysis of algorithms and problem complexity
05C80: Random graphs (graph-theoretic aspects)
90C27: Combinatorial optimization
60C05: Combinatorial probability
Related Items
Charting the replica symmetric phase, The replica symmetric phase of random constraint satisfaction problems, Sofic homological invariants and the Weak Pinsker Property, The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models, Constructing concrete hard instances of the maximum independent set problem, Factor of IID Percolation on Trees, The Interpolation Method for Random Graphs with Prescribed Degrees, The condensation transition in random hypergraph 2-coloring, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, The rank of sparse random matrices, Free energy subadditivity for symmetric random Hamiltonians, Large deviations of the greedy independent set algorithm on sparse random graphs, MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems, Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree, Percolation with small clusters on random graphs, A positive temperature phase transition in random hypergraph 2-coloring, Matchings on infinite graphs, Antiferromagnetic Potts model on the Erdős-Rényi random graph, Upper-bounding the \(k\)-colorability threshold by counting covers, Right-convergence of sparse random graphs, Perfect matchings as IID factors on non-amenable groups, Information-theoretic thresholds from the cavity method, Independence numbers of random sparse hypergraphs, Replica bounds by combinatorial interpolation for diluted spin systems, Convergence of maximum bisection ratio of sparse random graphs, Threshold saturation in spatially coupled constraint satisfaction problems, A scaling limit for the length of the longest cycle in a sparse random graph, Spin systems on Bethe lattices, On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model, The number of solutions for random regular NAE-SAT, Limit theory of combinatorial optimization for random geometric graphs, Typicality and entropy of processes on infinite trees, Optimal low-degree hardness of maximum independent set, On the maximal cut in a random hypergraph, General independence sets in random strongly sparse hypergraphs, Concentration of multi-overlaps for random dilute ferromagnetic spin models, Nearly subadditive sequences, Minimal contagious sets in random regular graphs, Universality of the mean-field for the Potts model, Limits of discrete distributions and Gibbs measures on random graphs, Maximum independent sets on random regular graphs, Suboptimality of local algorithms for a class of max-cut problems, Factor models on locally tree-like graphs, The replica symmetric solution for Potts models on \(d\)-regular graphs, Stack domination density, Lower bounds on the chromatic number of random graphs, Improved replica bounds for the independence ratio of random regular graphs, On the concentration of the independence numbers of random hypergraphs, Phase Transitions in Discrete Structures, On the concentration of the number of solutions of random satisfiability formulas, Harnessing the Bethe free energy, Independent Sets in Random Graphs from the Weighted Second Moment Method
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ising models on locally tree-like graphs
- Gibbs measures and phase transitions on sparse random graphs
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Bounds for diluted mean-fields spin glass models
- An introduction to covering problems for random walks on graphs
- The thermodynamic limit in mean field spin glass models
- Replica bounds for optimization problems and diluted spin systems
- Linear phase transition in random linear constraint satisfaction problems
- Factor models on locally tree-like graphs
- Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
- Percolation
- Dismantling Sparse Random Graphs
- Tight Bounds for LDPC and LDGM Codes Under MAP Decoding
- Sharp thresholds of graph properties, and the $k$-sat problem
- Random MAX SAT, random MAX CUT, and their phase transitions
- Sparse graphs: Metrics and random models
- Replica bounds for diluted non-Poissonian spin systems
