On the practically interesting instances of MAXCUT
  The complexity of a computational problem is traditionally quantified based
on the hardness of its worst case. This approach has many advantages and has
led to a deep and beautiful theory. However, from the practical perspective,
this leaves much to be desired. In application areas, practically interesting
instances very often occupy just a tiny part of an algorithm's space of
instances, and the vast majority of instances are simply irrelevant. Addressing
these issues is a major challenge for theoretical computer science which may
make theory more relevant to the practice of computer science.
  Following Bilu and Linial, we apply this perspective to MAXCUT, viewed as a
clustering problem. Using a variety of techniques, we investigate practically
interesting instances of this problem. Specifically, we show how to solve in
polynomial time distinguished, metric, expanding and dense instances of MAXCUT
under mild stability assumptions. In particular, $(1+\epsilon)$-stability
(which is optimal) suffices for metric and dense MAXCUT. We also show how to
solve in polynomial time $\Omega(\sqrt{n})$-stable instances of MAXCUT,
substantially improving the best previously known result.
