<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:0 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Aptos;
panose-1:2 11 0 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
mso-ligatures:none;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<div id="mail-editor-reference-message-container">
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102"> </span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica">Euiwoong Lee, PhD</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">University of Michigan</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"> <img width="139" height="209" style="width:1.4479in;height:2.177in" id="Picture_x0020_3" src="cid:image001.jpg@01DA4F76.C4170870" alt="My Photo"><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black;background:yellow">Monday, February 12, 2024 at 3:30pm</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black;background:yellow">Room – John Crerar Library 298</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Title:</span></i></b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121"> Recent progresses on Correlation Clustering</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Abstract:</span></i></b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121"> 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.<span class="apple-converted-space"> </span><br>
<br>
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.<br>
<br>
Joint work with Nairen Cao, Vincent Cohen-Addad, Shi Li, Alantha Newman, and Lukas Vogl</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Bio:</span></i></b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">
</span><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black">Euiwoong is an assistant professor in the<span class="apple-converted-space"> </span></span><a href="https://urldefense.com/v3/__https:/cse.engin.umich.edu/__;!!BpyFHLRN4TMTrA!8GQLm34LXNIAotKxVOepqWIwWrEnJedRBHmmfg6SHHBcyexCpEQ5_ZPcLRE7eIa5X1IhCg7FLtT9FLb9tTPN6x-4RA$"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black;text-decoration:none">Computer
Science and Engineering Division<span class="apple-converted-space"> </span></span></a><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black">at the<span class="apple-converted-space"> </span></span><a href="https://urldefense.com/v3/__https:/umich.edu__;!!BpyFHLRN4TMTrA!8GQLm34LXNIAotKxVOepqWIwWrEnJedRBHmmfg6SHHBcyexCpEQ5_ZPcLRE7eIa5X1IhCg7FLtT9FLb9tTM4Rfo6bw$"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black;text-decoration:none">University
of Michigan</span></a><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black">. Previously, he was a postdoc at New York University hosted by<span class="apple-converted-space"> </span></span><a href="https://urldefense.com/v3/__http:/cims.nyu.edu/*regev__;fg!!BpyFHLRN4TMTrA!8GQLm34LXNIAotKxVOepqWIwWrEnJedRBHmmfg6SHHBcyexCpEQ5_ZPcLRE7eIa5X1IhCg7FLtT9FLb9tTM6k-8ZAg$"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black;text-decoration:none">Oded
Regev</span></a><span class="apple-converted-space"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black"> </span></span><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black">and<span class="apple-converted-space"> </span></span><a href="https://urldefense.com/v3/__http:/cs.nyu.edu/*khot__;fg!!BpyFHLRN4TMTrA!8GQLm34LXNIAotKxVOepqWIwWrEnJedRBHmmfg6SHHBcyexCpEQ5_ZPcLRE7eIa5X1IhCg7FLtT9FLb9tTMS8DxAEQ$"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black;text-decoration:none">Subhash
Khot</span></a><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black">, and a research fellow at<span class="apple-converted-space"> </span></span><a href="https://urldefense.com/v3/__https:/simons.berkeley.edu__;!!BpyFHLRN4TMTrA!8GQLm34LXNIAotKxVOepqWIwWrEnJedRBHmmfg6SHHBcyexCpEQ5_ZPcLRE7eIa5X1IhCg7FLtT9FLb9tTNyq7AO3A$"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black;text-decoration:none">Simons
Institute for the Theory of Computing</span></a><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:black">.<span class="apple-converted-space"> </span></span><o:p></o:p></p>
<p><span style="color:black"> </span><o:p></o:p></p>
<p style="margin-bottom:12.0pt"><b><span style="font-size:12.0pt;font-family:Helvetica;color:black">Host:<span class="apple-converted-space"> Aaron Potechin</span></span></b><o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>