Local max-cut in smoothed polynomial time

DOI10.1145/3055399.3055402zbMath1369.68226arXiv1610.04807OpenAlexW2536358984MaRDI QIDQ4977991

Omer Angel, Fan Wei, Sébastien Bubeck, Yuval Peres

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

Nash equilibriumHopfield networkSherrington-Kirkpatrick modelpotential gamemax-cutsmoothed analysispolynomial running time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (6)

Smoothed analysis for tensor methods in unsupervised learning ⋮ Friendly bisections of random graphs ⋮ Local minima in disordered mean-field ferromagnets ⋮ Phase transition of degeneracy in minor-closed families ⋮ Zero-temperature dynamics in the dilute Curie-Weiss model ⋮ Local optima of the Sherrington-Kirkpatrick Hamiltonian

This page was built for publication: Local max-cut in smoothed polynomial time