Local max-cut in smoothed polynomial time (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-cutproblem for which no polynomial time method is known. In a breakthrough paper, Etscheid and R{“o}glin proved that the {em smoothed} complexity of local max-cut is quasi polynomial. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding locally optimal solutions for max-cut is much easier than solving it.

This is a joint work with Omer Angel, Sebastien Bubeck, and Yuval Peres.


2017-03-28   14:00 ~ 15:00   


Fan Wei, Stanford University


Room 308,School of Information Management & Engineering, Shanghai University of Finance & Economics