Pith. sign in

REVIEW 4 cited by

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2310.19594 v3 pith:SBTHAQAT submitted 2023-10-30 cs.DS cs.CC

Lukas Michel , Alex Scott This is my paper
classification cs.DScs.CC
keywords localsmoothedalgorithmanalysisflipmax-cutsearchalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

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.

Discussion (0). Sign in to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem

    cs.DS 2025-07 conditional novelty 8.0 of 10

    3-opt, 4-opt, and the 2.5-opt variant of the traveling salesman problem each have instances requiring exponentially many improving local-search iterations under every pivot rule.

  2. Binary constraints on one additional variable can create exponential ascents for local search

    cs.DM 2026-05 unverdicted novelty 7.0 of 10

    A star gadget with 2n triangles on one central variable in a binary VCSP produces an exponential ascent of length 10*2^n - 9 by intertwining two linear sublandscapes.

  3. Binary constraints on one additional variable can create exponential ascents for local search

    cs.DM 2026-05 conditional novelty 7.0 of 10

    A Boolean VCSP built as a star of 2n triangles on 4n+1 variables has an ascent of length 10·2^n − 9, despite having treedepth 3 and feedback vertex set number 1.

  4. All ascents exponential from valued constraint graphs of pathwidth three

    cs.DM 2026-01 unverdicted novelty 7.0 of 10

    A controlled doubling construction yields a pathwidth-three VCSP in which every ascent in the fitness landscape is exponentially long.

Pith tools