Exploring Smoothed Complexity of Local Max-Cut with Two Flips 🔍
Join Columbia University's Xi Chen as he unveils new insights into the smoothed complexity of the Local Max-Cut problem when limited to two flips, advancing our understanding in discrete mathematics and algorithm analysis.
Institute for Advanced Study
833 views • Nov 7, 2022
About this video
Computer Science/Discrete Mathematics Seminar I
Topic: Smoothed Complexity of Local Max-Cut with Two Flips
Speaker: Xi Chen
Affiliation: Columbia University
Date: November 07, 2022
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
Topic: Smoothed Complexity of Local Max-Cut with Two Flips
Speaker: Xi Chen
Affiliation: Columbia University
Date: November 07, 2022
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
Video Information
Views
833
Likes
14
Duration
57:44
Published
Nov 7, 2022