[Colloquium] [Talks at TTIC] REMINDER: 4/17 Research at TTIC: Yury Makarychev, TTIC

[Alicia McClarin]

*When:*     Friday, April 17th at 12:30pm; Room is open beginning at noon

*Where:*    Zoom Virtual Talk (see details below)

*Who: *      Yury Makarychev, TTIC

*Title: *      Perturbation Resilience and Certified Algorithms

*Abstract: * 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.

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.

The talk is based on a joint paper with Konstantin Makarychev.
----------------------------------------------------------------------------------------------------------

*Join Zoom Meeting*
https://zoom.us/j/482454649?pwd=THk3a1dOU1pURXRJN0psNUZwbFh1dz09

Meeting ID: 482 454 649
Password: 266123

Dial by your location
        +1 646 876 9923 US (New York)
        +1 312 626 6799 US (Chicago)
        +1 301 715 8592 US
        +1 346 248 7799 US (Houston)
        +1 408 638 0968 US (San Jose)
        +1 669 900 6833 US (San Jose)
        +1 253 215 8782 US

Meeting ID: 482 454 649
Find your local number: https://zoom.us/u/acS7ikRXC

********************************************************************************************

*Research at TTIC Seminar Series*

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.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact Nathan Srebro at nati at ttic.edu
<mcallester at ttic.edu>.

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave., **Office 504*
*Chicago, IL 60637*
*773-834-3321*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20200417/e31f795b/attachment.html>