SODA Conference 2018 Conference Paper
Voronoi tessellations in the CRT and continuum random maps of finite excess
- Louigi Addario-Berry
- Omer Angel
- Guillaume Chapuy
- Éric Fusy
- Christina Goldschmidt
Author name cluster
Omer Angel
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
1 author row
Possible papers
2STOC Conference 2017 Conference Paper
Local max-cut in smoothed polynomial time
- Omer Angel
- Sébastien Bubeck
- Yuval Peres
- Fan Wei
In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continued to amass, but formal proofs of this phenomenon have remained elusive. A canonical (and indeed complete) example is the local max-cut problem, for which no polynomial time method is known. In a breakthrough paper, Etscheid and Röglin proved that the smoothed complexity of local max-cut is quasi-polynomial, i.e., if arbitrary bounded weights are randomly perturbed, a local maximum can be found in ϕ n O (log n ) steps where ϕ is an upper bound on the random edge weight density. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding local optima for max-cut is much easier than solving it.