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

Abstract

We show that in random $K$-uniform hypergraphs of constant average degree, for even $K\ge 4$, local algorithms defined as factors of i.i.d. can not find nearly maximal cuts, when the average degree is sufficiently large. These algorithms have been used frequently to obtain lower bounds for the max-cut problem on random graphs, but it was not known whether they could be successful in finding nearly maximal cuts. This result follows from the fact that the overlap of any two nearly maximal cuts in such hypergraphs does not take values in a certain non-trivial interval - a phenomenon referred to as the overlap gap property - which is proved by comparing diluted models with large average degree with appropriate fully connected spin glass models and showing the overlap gap property in the latter setting.

Final version; to appear in Ann. Probab

References in corpus (6)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• The high temperature region of the Viana-Bray diluted spin glass model
• Spectral gap estimates in mean field spin glasses
• On the energy landscape of the mixed even $p$-spin model
• A connection between MAX $\kappa$-CUT and the inhomogeneous Potts spin glass in the large degree limit
• Optimization on Sparse Random Hypergraphs and Spin Glasses

Cited by in corpus (26)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Computational Barriers to Estimation from Low-Degree Polynomials
• Disordered Systems Insights on Computational Hardness
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Algorithmic Thresholds in Mean Field Spin Glasses
• Optimizing Mean Field Spin Glasses with External Field
• The Overlap Gap Property in Principal Submatrix Recovery
• Surfing on minima of isostatic landscapes: avalanches and unjamming transition
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• Optimization on Sparse Random Hypergraphs and Spin Glasses
• (Dis)assortative Partitions on Random Regular Graphs
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Combinatorial NLTS From the Overlap Gap Property
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• Sampling from Mean-Field Gibbs Measures via Diffusion Processes
• The Overlap Gap Property limits limit swapping in the QAOA
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Free Energy Subadditivity for Symmetric Random Hamiltonians
• Improving the Quantum Approximate Optimization Algorithm with postselection