  Local search algorithms for NP-hard problems such as Max-Cut frequently
perform much better in practice than worst-case analysis suggests. Smoothed
analysis has proved an effective approach to understanding this: a substantial
literature shows that when a small amount of random noise is added to input
data, local search algorithms typically run in polynomial or quasi-polynomial
time. In this paper, we provide the first example where a local search
algorithm for the Max-Cut problem fails to be efficient in the framework of
smoothed analysis. Specifically, we construct a graph with $n$ vertices where
the smoothed runtime of the 3-FLIP algorithm can be as large as
$2^{\Omega(\sqrt{n})}$.
  Additionally, for the setting without random noise, we give a new
construction of graphs where the runtime of the FLIP algorithm is
$2^{\Omega(n)}$ for any pivot rule. These graphs are much smaller and have a
simpler structure than previous constructions.
