# Smoothed complexity of local Max-Cut and binary Max-CSP

arXiv: https://arxiv.org/abs/1911.10381 · HTML: https://mlsanity.com/paper/1911.10381/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Nov 2019.

## Built on by (most cited first, 1 of 1)

- [Smoothed Analysis of Inconsistent A*](https://mlsanity.com/paper/2609.23680/) (2026)

## Abstract (arXiv)

We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most smashφ n^O(√log n), where n is the number of nodes in the graph and φ is a parameter that measures the magnitude of perturbations applied on its edge weights. This improves the previously best upper bound of φ nO(log n) by Etscheid and R"oglin. Our result is based on an analysis of long sequences of flips, which shows~that~it is very unlikely for every flip in a long sequence to incur a positive but small improvement in the cut weight. We also extend the same upper bound on the smoothed complexity of FLIP to all binary Maximum Constraint Satisfaction Problems.