Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
From MaRDI portal
Publication:6076731
DOI10.1002/rsa.21149zbMath1529.05128arXiv2111.06813OpenAlexW3214063368MaRDI QIDQ6076731
No author found.
Publication date: 17 October 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2111.06813
Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Right-convergence of sparse random graphs
- Variational representations for the Parisi functional and the two-dimensional Guerra-Talagrand bound
- Parisi formula for the ground state energy in the mixed \(p\)-spin model
- Convergence of maximum bisection ratio of sparse random graphs
- Optimization of mean-field spin glasses
- The Parisi formula has a unique minimizer
- Extremal cuts of sparse random graphs
- The Parisi formula
- A dynamic programming approach to the Parisi functional
- Invariant Gaussian processes and independent sets on regular graphs of large girth
- Ramanujan graphings and correlation decay in local algorithms
- A proof of Alon’s second eigenvalue conjecture and related problems
- Probability
- On the max‐cut of sparse random graphs
- How well do local algorithms solve semidefinite programs?
- Optimization of the Sherrington--Kirkpatrick Hamiltonian
- The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
- The Interpolation Method for Random Graphs with Prescribed Degrees
- Factors of IID on Trees
- The Ising Antiferromagnet and Max Cut on Random Regular Graphs
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
