TCS+ talk: Wednesday, November 20 — Jason Li, CMU

by plustcs

The next TCS+ talk will take place this coming Wednesday, November 20th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Jason Li from CMU will speak about “The Karger-Stein Algorithm is Optimal for k-cut” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum k-cut in time approximately O(n^{2k-2}). The best lower bounds come from conjectures about the solvability of the k-clique problem and a reduction from k-clique to k-cut, and show that solving k-cut is likely to require time \Omega(n^k). Our recent results have given special-purpose algorithms that solve the problem in time n^{1.98k + O(1)}, and ones that have better performance for special classes of graphs (e.g., for small integer weights).