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 -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 -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 connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum -cut in time approximately . The best lower bounds come from conjectures about the solvability of the -clique problem and a reduction from -clique to -cut, and show that solving -cut is likely to require time . Our recent results have given special-purpose algorithms that solve the problem in time , and ones that have better performance for special classes of graphs (e.g., for small integer weights).