[Theory] REMINDER: 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>*


On Wed, Jan 15, 2020 at 4:55 PM Mary Marre <mmarre at ttic.edu> wrote:

> *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/20200122/b07b5270/attachment-0001.html>