Published on November 14, 2016 by Microsoft Research
Want create site? Find Free WordPress Themes and plugins.

The local max-cut problem asks to find a partition of the vertices in a weighted graph such that the cut weight cannot be improved by moving a single vertex (that is the partition is locally optimal). This comes up naturally, for example, in computing Nash equilibrium for the party affiliation game. It is well-known that the natural local search algorithm for this problem might take exponential time to reach a locally optimal solution. We show that adding a little bit of noise to the weights tames this exponential into a polynomial. In particular we show that local max-cut is in smoothed polynomial time (this improves the recent quasi-polynomial result of Etscheid and Roglin). Joint work with Omer Angel, Yuval Peres, and Fan Wei.

See more on this video at

Did you find apk for android? You can find new Free Android Games and apps.

Leave a Reply

1 Comment on "Northwest Probability Seminar – Session 3"

Notify of

Tom Hutchcroft
Tom Hutchcroft
10 months 20 hours ago

Slides from the talk are available on my website