[Theory] [Theory Lunch] Aravind Reddy, Wednesday 11/9 12:30pm-1:30pm, JCL 298.

[Antares Chen]

Hey everyone,

Just wanted to let folks know that we do have theory lunch this week!
Deeply sorry for sending this announcement out so late.

Best,
Antares

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

*Date**:* November 9, 2022
*Time: *12:30pm CT
*Location: *JCL 298

Speaker: Aravind Reddy <https://aravindreddy.org/>

*Title: *Uniform Metric Labeling of  Perturbation Resilient Instances

*Zoom: *[link
<https://uchicago.zoom.us/j/94843270509?pwd=am9RMW5jeHJsblVCekN6bmwzM3dlZz09>
]

*Abstract:* 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 book chapter by Makarychev and Makarychev
<https://home.ttic.edu/~yury/papers/bwca.pdf> 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
2018 <http://proceedings.mlr.press/v84/lang18a.html>, 2019
<https://proceedings.mlr.press/v89/lang19a.html>, and 2021
<http://proceedings.mlr.press/v130/lang21a/lang21a.pdf>.

[Theory Lunch Webpage
<https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAswwp_F5nRs$>
]
[Theory Lunch Calendar
<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$>
]

************************************************************
**************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221109/a5c45d77/attachment-0001.html>