[Theory] 1/22 Talks at TTIC: David Wajc, Carnegie Mellon University

[Mary Marre]

*When:*      Wednesday, January 22nd at 11:00 am



*Where:*     TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who: *        David Wajc, Carnegie Mellon University


*Title:         *Randomized Rounding in the Face of Uncertainty

*Abstract:* Historically, optimization in computer science has been studied
in the full information setting: data is collected, a program is run, and
then the output is used. Vast theories of algorithms were developed,
leading to a large toolkit for solving problems in such full-information
settings. However, the increasing pervasiveness of user-facing applications
is shifting the focus toward incomplete-information computational models:
data is generated by users and thus revealed over time, while the same
users expect their new datum to affect the externalized solution quickly,
if not immediately. This uncertainty about the input and urgency of
response to changes in said input pose new challenges not faced in the
full-information setting. As such, new approaches are needed to capture the
power of computation under uncertainty.

In this talk I will outline some of my work towards better characterizing
the power of computation in the face of uncertainty. In particular, I will
focus on my work on randomized rounding in online and dynamic settings.
Along the way, I will discuss some of my results, including resolutions of
several longstanding open problems in the field of online algorithms, and
the first randomized dynamic matching algorithms that work against an
adaptive adversary.


Host: Avrim Blum <avrim at ttic.edu>




Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20200115/9f1bb870/attachment-0001.html>