<div dir="ltr"><div><div><div dir="ltr"><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif">Hey everyone,</span></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif"><br></span></div><div style="">Just wanted to let folks know that we do have theory lunch this week! Deeply sorry for sending this announcement out so late.</div><div style=""><br></div><div style="">Best,</div><div style="">Antares</div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif;font-size:large"><br></span></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">******************************</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">******************************</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">**************************</span><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></b></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></b></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4">Date</font></b><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;font-size:1.13em;color:rgb(49,49,49);word-spacing:1px">:</b><span style="font-size:1.13em;color:rgb(49,49,49);word-spacing:1px"> </span><span style="color:rgb(49,49,49);word-spacing:1px"><font size="4">November 9, 2022</font></span><br></div><div><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="color:rgb(32,31,30);margin:0px"><div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Time: </b>12:30pm CT</font></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Location: </b>JCL 298</font></div><div dir="auto" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><b><font style="font-size:1.13em"><br></font></b></div><div dir="auto" style="margin:0px;color:rgb(49,49,49);word-spacing:1px"><font size="4"><font face="Calibri, Arial, Helvetica, sans-serif" style="font-weight:bold">Speaker: </font><font face="Arial"><a href="https://aravindreddy.org/" target="_blank">Aravind Reddy</a></font></font></div><div dir="auto" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></div></div><div style="margin:0px"><span style="color:rgb(49,49,49);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;word-spacing:1px"><font style="font-size:1.13em"><b>Title: </b></font></span><span style="font-family:Slack-Lato,Slack-Fractions,appleLogo,sans-serif;font-variant-ligatures:common-ligatures;background-color:rgb(255,255,255)"><font size="4" style="" color="#000000">Uniform Metric Labeling of  Perturbation Resilient Instances</font></span></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><b style="color:rgb(49,49,49);font-size:16px;word-spacing:1px"><font style="font-size:1.13em"><br></font></b></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><span style="margin:0px;font-size:16px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Zoom: </b>[<a href="https://uchicago.zoom.us/j/94843270509?pwd=am9RMW5jeHJsblVCekN6bmwzM3dlZz09" target="_blank">link</a>]</font></span></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><br></div><div style="margin:0px"><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="color:rgb(49,49,49);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:13pt;margin:0px"><b>Abstract:</b></span><span style="color:rgb(32,31,30);font-family:"trebuchet ms",sans-serif;font-size:12pt;margin:0px;word-spacing:0px"> </span></font><font size="4" style="background-color:rgb(255,255,255)" color="#000000"><span style="font-family:Slack-Lato,Slack-Fractions,appleLogo,sans-serif;font-variant-ligatures:common-ligatures">Metric labeling is a well-studied generalization of the classic minimum s-t cut problem, which was introduced by Kleinberg and Tardos (JACM 2002). In this talk, we will discuss some recent beyond worst-case analysis results on a popular linear programming formulation of this problem. In particular, we will discuss results on instances which are Perturbation-Resilient. Perturbation-resilience (also known as Bilu-Linial stability) is a popular model for beyond worst-case analysis of approximation algorithms (see </span><a target="_blank" class="gmail-c-link" href="https://home.ttic.edu/~yury/papers/bwca.pdf" rel="noopener noreferrer" tabindex="-1" style="box-sizing:inherit;text-decoration-line:none;font-family:Slack-Lato,Slack-Fractions,appleLogo,sans-serif;font-variant-ligatures:common-ligatures">book chapter by Makarychev and Makarychev</a><span style="font-family:Slack-Lato,Slack-Fractions,appleLogo,sans-serif;font-variant-ligatures:common-ligatures"> for an introduction). This talk will be based on a series of works by me and my collaborators (Hunter Lang, Aravindan Vijayaraghavan, and David Sontag) which appeared in AISTATS </span><a target="_blank" class="gmail-c-link" href="http://proceedings.mlr.press/v84/lang18a.html" rel="noopener noreferrer" tabindex="-1" style="box-sizing:inherit;text-decoration-line:none;font-family:Slack-Lato,Slack-Fractions,appleLogo,sans-serif;font-variant-ligatures:common-ligatures">2018</a><span style="font-family:Slack-Lato,Slack-Fractions,appleLogo,sans-serif;font-variant-ligatures:common-ligatures">, </span><a target="_blank" class="gmail-c-link" href="https://proceedings.mlr.press/v89/lang19a.html" rel="noopener noreferrer" tabindex="-1" style="box-sizing:inherit;text-decoration-line:none;font-family:Slack-Lato,Slack-Fractions,appleLogo,sans-serif;font-variant-ligatures:common-ligatures">2019</a><span style="font-family:Slack-Lato,Slack-Fractions,appleLogo,sans-serif;font-variant-ligatures:common-ligatures">, and </span><a target="_blank" class="gmail-c-link" href="http://proceedings.mlr.press/v130/lang21a/lang21a.pdf" rel="noopener noreferrer" tabindex="-1" style="box-sizing:inherit;text-decoration-line:none;font-family:Slack-Lato,Slack-Fractions,appleLogo,sans-serif;font-variant-ligatures:common-ligatures">2021</a><span style="font-family:Slack-Lato,Slack-Fractions,appleLogo,sans-serif;font-variant-ligatures:common-ligatures">.</span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><font size="4"><br></font></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">[</span><a href="https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAswwp_F5nRs$" rel="noopener noreferrer" title="https://orecchia.net/event/theory-lunch/" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large;margin:0px" target="_blank"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Theory</span></span></span></span></span> <span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Lunch</span></span></span></span> Webpage</a><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">]</span><br style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">[</span><a href="https://urldefense.com/v3/__https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America*Chicago__;Lw!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAsww4XtIRnQ$" rel="noopener noreferrer" title="https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large;margin:0px" target="_blank"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Theory</span></span></span></span></span></span></span><span style="margin:0px"> </span><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Lunch</span></span></span></span></span><span style="margin:0px"> </span>Calendar</a><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">]</span></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large"><br></span></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="font-size:large">******************************</span><span style="font-size:large">******************************</span><span style="font-size:large">**************************</span><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large"><br></span></span></font></div></div></div></div></div></div></div></div></div>
</div>
</div>
</div>