  Finding locally optimal solutions for max-cut and max-$k$-cut are well-known
PLS-complete problems. An instinctive approach to finding such a locally
optimum solution is the FLIP method. Even though FLIP requires exponential time
in worst-case instances, it tends to terminate quickly in practical instances.
To explain this discrepancy, the run-time of FLIP has been studied in the
smoothed complexity framework. Etscheid and R\"{o}glin showed that the smoothed
complexity of FLIP for max-cut in arbitrary graphs is quasi-polynomial. Angel,
Bubeck, Peres, and Wei showed that the smoothed complexity of FLIP for max-cut
in complete graphs is $O(\phi^5n^{15.1})$, where $\phi$ is an upper bound on
the random edge-weight density and $n$ is the number of vertices in the input
graph.
  While Angel et al.'s result showed the first polynomial smoothed complexity,
they also conjectured that their run-time bound is far from optimal. In this
work, we make substantial progress towards improving the run-time bound. We
prove that the smoothed complexity of FLIP in complete graphs is $O(\phi
n^{7.83})$. Our results are based on a carefully chosen matrix whose rank
captures the run-time of the method along with improved rank bounds for this
matrix and an improved union bound based on this matrix. In addition, our
techniques provide a general framework for analyzing FLIP in the smoothed
framework. We illustrate this general framework by showing that the smoothed
complexity of FLIP for max-$3$-cut in complete graphs is polynomial and for
max-$k$-cut in arbitrary graphs is quasi-polynomial. We believe that our
techniques should also be of interest towards addressing the smoothed
complexity of FLIP for max-$k$-cut in complete graphs for larger constants $k$.
