Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
From MaRDI portal
Publication:5891427
DOI10.1145/1806689.1806706zbMath1293.05350arXiv0912.2444OpenAlexW2130042807WikidataQ106094403 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
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27) Combinatorial probability (60C05)
Related Items
On the maximal cut in a random hypergraph, Universality of the mean-field for the Potts model, Percolation with small clusters on random graphs, A positive temperature phase transition in random hypergraph 2-coloring, The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models, Factor of IID Percolation on Trees, Stack domination density, Information-theoretic thresholds from the cavity method, On the concentration of the number of solutions of random satisfiability formulas, Limits of discrete distributions and Gibbs measures on random graphs, Maximum independent sets on random regular graphs, Matchings on infinite graphs, Antiferromagnetic Potts model on the Erdős-Rényi random graph, Upper-bounding the \(k\)-colorability threshold by counting covers, 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, Lower bounds on the chromatic number of random graphs, Harnessing the Bethe free energy, Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree, Suboptimality of local algorithms for a class of max-cut problems, General independence sets in random strongly sparse hypergraphs, Independence numbers of random sparse hypergraphs, Concentration of multi-overlaps for random dilute ferromagnetic spin models, Algorithmic obstructions in the random number partitioning problem, Improved replica bounds for the independence ratio of random regular graphs, On the concentration of the independence numbers of random hypergraphs, Sharp thresholds in adaptive random graph processes, Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics, The Interpolation Method for Random Graphs with Prescribed Degrees, Threshold saturation in spatially coupled constraint satisfaction problems, Factor models on locally tree-like graphs, Perfect matchings as IID factors on non-amenable groups, Nearly subadditive sequences, The replica symmetric solution for Potts models on \(d\)-regular graphs, Right-convergence of sparse random graphs, Constructing concrete hard instances of the maximum independent set problem, Charting the replica symmetric phase, A scaling limit for the length of the longest cycle in a sparse random graph, Replica bounds by combinatorial interpolation for diluted spin systems, Spin systems on Bethe lattices, On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model, Convergence of maximum bisection ratio of sparse random graphs, Phase Transitions in Discrete Structures, Independent Sets in Random Graphs from the Weighted Second Moment Method, The condensation transition in random hypergraph 2-coloring, The number of solutions for random regular NAE-SAT, Limit theory of combinatorial optimization for random geometric graphs, The replica symmetric phase of random constraint satisfaction problems, Typicality and entropy of processes on infinite trees, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, The rank of sparse random matrices, Minimal contagious sets in random regular graphs, Sofic homological invariants and the Weak Pinsker Property, Optimal low-degree hardness of maximum independent set
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
