Suboptimality of local algorithms for a class of max-cut problems

DOI10.1214/18-AOP1291zbMath1466.60200arXiv1707.05386WikidataQ127945773 ScholiaQ127945773MaRDI QIDQ2421823

Wei-Kuo Chen, David Gamarnik, Mustazee Rahman, Dmitriy Panchenko

Publication date: 18 June 2019

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.05386

zbMATH Keywords

spin glasseslocal algorithmsmaximum cut problems

Mathematics Subject Classification ID

Gaussian processes (60G15) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Large deviations (60F10) Randomized algorithms (68W20)

Related Items

Disordered systems insights on computational hardness, Computational barriers to estimation from low-degree polynomials, Asymptotic bounds on total domination in regular graphs, The algorithmic hardness threshold for continuous random energy models, Free energy subadditivity for symmetric random Hamiltonians, Generalized TAP Free Energy, Combinatorics. Abstracts from the workshop held January 1--7, 2023, Free Energy Wells and Overlap Gap Property in Sparse PCA, Algorithmic obstructions in the random number partitioning problem, Optimizing mean field spin glasses with external field, Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics, The overlap gap property and approximate message passing algorithms for \(p\)-spin models, Network models: structure and function. Abstracts from the workshop held December 10--16, 2017, On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model, The overlap gap property in principal submatrix recovery, Optimization of mean-field spin glasses, Minimum 2-dominating sets in regular graphs, Surfing on minima of isostatic landscapes: avalanches and unjamming transition, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, Optimal low-degree hardness of maximum independent set, (Dis)assortative partitions on random regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Perfect matchings as IID factors on non-amenable groups
• 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
• Independence ratio and random eigenvectors in transitive graphs
• The high temperature region of the Viana-Bray diluted spin glass model
• On the energy landscape of the mixed even \(p\)-spin model
• Disorder chaos in some diluted spin Glass models
• MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
• Spectral gap estimates in mean field spin glasses
• Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
• Local algorithms, regular graphs of large girth, and random regular graphs
• Bounds for diluted mean-fields spin glass models
• The thermodynamic limit in mean field spin glass models
• Replica bounds for optimization problems and diluted spin systems
• Broken replica symmetry bounds in the mean field spin glass model
• The Parisi ultrametricity conjecture
• Local algorithms for independent sets are half-optimal
• The Parisi formula has a unique minimizer
• Extremal cuts of sparse random graphs
• The Parisi formula for mixed \(p\)-spin models
• Limits of locally-globally convergent graph sequences
• Controlled Markov processes and viscosity solutions
• The Parisi formula
• Random multi-overlap structures and cavity fields in diluted spin glasses
• A dynamic programming approach to the Parisi functional
• Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
• Borel oracles. An analytical approach to constant-time algorithms
• Differentiation of Real Functions
• On the K‐sat model with large number of clauses
• The Sherrington-Kirkpatrick Model
• On large‐girth regular graphs and random processes on trees
• How well do local algorithms solve semidefinite programs?
• The SK Model Is Infinite Step Replica Symmetry Breaking at Zero Temperature
• Factor of IID Percolation on Trees
• Factors of IID on Trees
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• Mean Field Models for Spin Glasses
• Limits of local algorithms over sparse random graphs