Smoothed Complexity of Local Max-Cut with Two Flips

Many algorithms and heuristics that work well in practice have poor performance under the worst-case analysis, due to delicate pathological instances that one may never encounter. To bridge this theory-practice gap, Spielman and Teng introduced the smoothed analysis framework which can be viewed as a hybrid of the classical worst-case and average-case analyses. Since then, the smoothed analysis of algorithms and problems from combinatorial optimization, among many other areas, has been studied extensively.

In this talk, we will review progress on the smoothed complexity of the FLIP algorithm for local Max-Cut and binary Maximum Constraint Satisfaction Problems. We will then discuss new results for the situation when the algorithm is allowed to make two flips in each step.

Based on joint work with Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Mihalis Yannakakis and Xinzhi Zhang