[Colloquium] CS Theory Seminar - Euiwoong Lee, February 12, 2024

[Jose J Fragoso]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Euiwoong Lee, PhD
University of Michigan

 [My Photo]


Monday, February 12, 2024 at 3:30pm
Room – John Crerar Library 298


Title: Recent progresses on Correlation Clustering

Abstract: Correlation Clustering is one of the most well-studied graph clustering problems. The input is a complete graph where each edge is labeled either "+" or "-", and the goal is to partition the vertex set into (an arbitrary number of) clusters to minimize (the number of + edges between different clusters) + (the number of - edges within the same cluster). Until recently, the best polynomial-time approximation ratio was 2.06, nearly matching the integrality gap of 2 for the standard LP relaxation.

Since 2022, we have bypassed this barrier and progressively improved the approximation ratio, with the current ratio being 1.44. Based on a new relaxation inspired by the Sherali-Adams hierarchy, the algorithm introduces and combines several tools considered in different contexts, including "local to global correlation rounding" and "combinatorial preclusering". In this talk, I will describe the current algorithm as well as how it has been inspired by various viewpoints.

Joint work with Nairen Cao, Vincent Cohen-Addad, Shi Li, Alantha Newman, and Lukas Vogl

Bio: Euiwoong is an assistant professor in the Computer Science and Engineering Division <https://urldefense.com/v3/__https:/cse.engin.umich.edu/__;!!BpyFHLRN4TMTrA!8GQLm34LXNIAotKxVOepqWIwWrEnJedRBHmmfg6SHHBcyexCpEQ5_ZPcLRE7eIa5X1IhCg7FLtT9FLb9tTPN6x-4RA$> at the University of Michigan<https://urldefense.com/v3/__https:/umich.edu__;!!BpyFHLRN4TMTrA!8GQLm34LXNIAotKxVOepqWIwWrEnJedRBHmmfg6SHHBcyexCpEQ5_ZPcLRE7eIa5X1IhCg7FLtT9FLb9tTM4Rfo6bw$>. Previously, he was a postdoc at New York University hosted by Oded Regev<https://urldefense.com/v3/__http:/cims.nyu.edu/*regev__;fg!!BpyFHLRN4TMTrA!8GQLm34LXNIAotKxVOepqWIwWrEnJedRBHmmfg6SHHBcyexCpEQ5_ZPcLRE7eIa5X1IhCg7FLtT9FLb9tTM6k-8ZAg$> and Subhash Khot<https://urldefense.com/v3/__http:/cs.nyu.edu/*khot__;fg!!BpyFHLRN4TMTrA!8GQLm34LXNIAotKxVOepqWIwWrEnJedRBHmmfg6SHHBcyexCpEQ5_ZPcLRE7eIa5X1IhCg7FLtT9FLb9tTMS8DxAEQ$>, and a research fellow at Simons Institute for the Theory of Computing<https://urldefense.com/v3/__https:/simons.berkeley.edu__;!!BpyFHLRN4TMTrA!8GQLm34LXNIAotKxVOepqWIwWrEnJedRBHmmfg6SHHBcyexCpEQ5_ZPcLRE7eIa5X1IhCg7FLtT9FLb9tTNyq7AO3A$>.



Host: Aaron Potechin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240201/cd130b75/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 1647163 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240201/cd130b75/attachment-0001.jpg>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00001.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240201/cd130b75/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00002.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240201/cd130b75/attachment-0003.txt>