Publications [#372539] of Fan Wei

Papers Published

1. Angel, O; Bubeck, S; Peres, Y; Wei, F, Local max-cut in smoothed polynomial time, Proceedings of the Annual ACM Symposium on Theory of Computing, vol. Part F128415 (June, 2017), pp. 429-437, ISBN 9781450345286 [doi]
   (last updated on 2026/01/16)

   Abstract:
   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(loh 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.