The Ising Antiferromagnet and Max Cut on Random Regular Graphs
From MaRDI portal
Publication:5864219
DOI10.1137/20M137999XMaRDI QIDQ5864219
Amin Coja-Oghlan, Balázs F. Mezei, Philipp Loick, Gregory B. Sorkin
Publication date: 3 June 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2009.10483
Related Items (3)
Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree ⋮ On the minimum bisection of random 3-regular graphs ⋮ Metastability of the Potts ferromagnet on random regular graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Consistency thresholds for the planted bisection model
- Belief propagation, robust reconstruction and optimal recovery of block models
- Spin glass models from the point of view of spin distributions
- Reconstruction and estimation in the planted partition model
- On the chromatic number of random regular graphs
- Ising models on locally tree-like graphs
- The high temperature region of the Viana-Bray diluted spin glass model
- Remarks on the limiting Gibbs states on a (d+1)-tree
- On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
- Information-theoretic thresholds from the cavity method
- A proof of the block model threshold conjecture
- Charting the replica symmetric phase
- Bounds for diluted mean-fields spin glass models
- Replica bounds for optimization problems and diluted spin systems
- Broken replica symmetry bounds in the mean field spin glass model
- The cavity method at zero temperature
- Bounds on the max and min bisection of random cubic and random 4-regular graphs
- The Parisi ultrametricity conjecture
- Spin systems on Bethe lattices
- Bounds on the bisection width for random \(d\)-regular graphs
- Extremal cuts of sparse random graphs
- Factor models on locally tree-like graphs
- The replica symmetric solution for Potts models on \(d\)-regular graphs
- The Parisi formula
- Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
- Improved approximation of Max-Cut on graphs of bounded degree
- Invariant Gaussian processes and independent sets on regular graphs of large girth
- On the power of unique 2-prover 1-round games
- Information, Physics, and Computation
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Community Detection and Stochastic Block Models
- On the max‐cut of sparse random graphs
- Proof of the Achievability Conjectures for the General Stochastic Block Model
- Sum-of-squares proofs and the quest toward optimal algorithms
- Random MAX SAT, random MAX CUT, and their phase transitions
- The Sherrington-Kirkpatrick Model
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- Community detection thresholds and the weak Ramanujan property
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Semidefinite programs on sparse random graphs and their application to community detection
- Statistical Mechanics of Lattice Systems
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Some optimal inapproximability results
- MAX k‐CUT and approximating the chromatic number of random graphs
- Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
This page was built for publication: The Ising Antiferromagnet and Max Cut on Random Regular Graphs
