<div dir="ltr"><div><font face="arial, sans-serif" style="color:rgb(0,0,0)"><b>When:</b>     Friday, April 17th at 12:30pm; Room is open beginning at noon</font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Where:</b>    Zoom Virtual Talk (see details below)<br></font></div><div><div style="color:rgb(0,0,0)"><p style="margin-bottom:0.0001pt;line-height:normal"><font face="arial, sans-serif"><b>Who: </b>     <b> </b></font>Yury Makarychev, TTIC</p><table cellpadding="0" style="border-collapse:collapse;margin-top:0px;width:auto;font-size:0.875rem;letter-spacing:0.2px;display:block"></table></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Title: </b>      </font><span style="color:rgb(34,34,34)"><font face="arial, sans-serif">Perturbation Resilience and Certified Algorithms</font></span></div><div style="color:rgb(0,0,0)"><span style="color:rgb(34,34,34)"><font face="arial, sans-serif"><br></font></span></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Abstract: </b> <span style="color:rgb(34,34,34)">We will first define and discuss the notion of perturbation resilience that aims to capture real-life instances. We will see that perturbation-resilient instances of several clustering and combinatorial optimization problems – that are NP-hard in the worst case – can be solved in polynomial time. Specifically, we will define a new class of algorithms – certified algorithms – and prove that they exactly solve perturbation-resilient instances and, additionally, find an approximate solution for arbitrary (worst-case) instances. Further, we will see that certified algorithms have a number of other desirable properties.</span><span style="color:rgb(34,34,34)"><br></span></font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">We will present a framework for designing certified algorithms, provide examples of certified algorithms for Max Cut/Min Uncut, Minimum Multiway Cut, k-medians and k-means. </font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">The talk is based on a joint paper with Konstantin Makarychev.</font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif">----------------------------------------------------------------------------------------------------------</font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div><div><b>Join Zoom Meeting</b><br><a href="https://zoom.us/j/482454649?pwd=THk3a1dOU1pURXRJN0psNUZwbFh1dz09" target="_blank">https://zoom.us/j/482454649?pwd=THk3a1dOU1pURXRJN0psNUZwbFh1dz09</a><br><br>Meeting ID: 482 454 649<br>Password: 266123<br><br>Dial by your location<br>        +1 646 876 9923 US (New York)<br>        +1 312 626 6799 US (Chicago)<br>        +1 301 715 8592 US<br>        +1 346 248 7799 US (Houston)<br>        +1 408 638 0968 US (San Jose)<br>        +1 669 900 6833 US (San Jose)<br>        +1 253 215 8782 US</div><div><br>Meeting ID: 482 454 649<br>Find your local number: <a href="https://zoom.us/u/acS7ikRXC" target="_blank">https://zoom.us/u/acS7ikRXC</a></div></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div></div><div style="color:rgb(0,0,0)"><div style="font-size:13px;margin:0px;line-height:normal"><font face="arial, sans-serif"><b style="font-size:12.8px">******************************************************************************************************</b><br></font></div><div style="font-size:13px;margin:0px;line-height:normal"><div style="font-size:12.8px"><b><font face="arial, sans-serif"><br></font></b></div><div style="font-size:12.8px"><b><font face="arial, sans-serif">Research at TTIC Seminar Series</font></b></div><div style="font-size:12.8px"><font face="arial, sans-serif"> </font></div><div style="font-size:12.8px"><font face="arial, sans-serif">TTIC is hosting a weekly seminar series presenting the research currently underway at the Institute. Every week a different TTIC faculty member will present their research.  The lectures are intended both for students seeking research topics and adviser, and for the general TTIC and University of Chicago communities interested in hearing what their colleagues are up to.   </font></div><div style="font-size:12.8px"><font face="arial, sans-serif"> </font></div><div style="font-size:12.8px"><font face="arial, sans-serif">To receive announcements about the seminar series, please subscribe to the mailing list: <a href="https://groups.google.com/a/ttic.edu/group/talks/subscribe" target="_blank" style="text-decoration-line:none">https://groups.google.com/a/ttic.edu/group/talks/subscribe</a></font></div><div style="font-size:12.8px"><font face="arial, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, sans-serif">Speaker details can be found at: <a href="http://www.ttic.edu/tticseminar.php" target="_blank" style="text-decoration-line:none">http://www.ttic.edu/tticseminar.php</a>.</font></div><div style="font-size:12.8px"><font face="arial, sans-serif"> </font></div><div style="font-size:12.8px"><font face="arial, sans-serif">For additional questions, please contact Nathan Srebro at <a href="mailto:mcallester@ttic.edu" target="_blank" style="text-decoration-line:none">nati@ttic.edu</a>.</font></div></div></div><font color="#888888"><div><br></div></font><div><br></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><b><font color="#0b5394">Alicia McClarin</font></b><div><div><font color="#0b5394"><i>Toyota Technological Institute at Chicago</i></font></div><div><div><font color="#0b5394"><i>6045 S. Kenwood Ave., </i></font><i style="color:rgb(11,83,148)">Office 504</i></div><div><i style="color:rgb(11,83,148)">Chicago, IL 60637</i><br></div></div><div><i style="color:rgb(11,83,148)">773-834-3321</i><i style="color:rgb(11,83,148)"><br></i></div><div><a href="http://www.ttic.edu/" target="_blank"><font color="#0b5394"><i>www.ttic.edu</i></font></a></div></div></div></div></div></div></div></div></div></div></div></div>