<div dir="ltr"><div dir="ltr"><div class="gmail_default" style=""><div class="gmail_default" style=""><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif" style=""><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b style="">When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Wednesday, January 22nd at 11:00 am</font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;text-align:justify;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>        </font></font>David Wajc, Carnegie Mellon University</font></p></div><div class="gmail_default" style=""><font face="arial, sans-serif"><br></font></div><div class="gmail_default" style=""><b><font face="arial, sans-serif"><br></font></b></div><div class="gmail_default" style=""><font face="arial, sans-serif"><b>Title:         </b>Randomized Rounding in the Face of Uncertainty<br></font></div><div class="gmail_default" style=""><div style=""><b><font face="arial, sans-serif"><br></font></b></div><div style=""><font face="arial, sans-serif"><b>Abstract:</b> 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. </font></div><div style=""><font face="arial, sans-serif"><br></font></div><div style=""><font face="arial, sans-serif">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.</font></div><div style=""><font face="arial, sans-serif"><br></font></div><div style=""><font face="arial, sans-serif"><br></font></div><div style=""><font face="arial, sans-serif">Host: <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a></font></div><div style=""><br></div><div style=""><br></div><div><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div></div></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jan 15, 2020 at 4:55 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><p style="font-size:small;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Wednesday, January 22nd at 11:00 am</font></font><br></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></font></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="text-align:justify;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" style="font-size:small"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>        </font></font>David Wajc, Carnegie Mellon University</font></p></div><div style="font-size:small"><font face="arial, sans-serif"><br></font></div><div style="font-size:small"><b><font face="arial, sans-serif"><br></font></b></div><div style="font-size:small"><font face="arial, sans-serif"><b>Title:         </b>Randomized Rounding in the Face of Uncertainty<br></font></div><div style="font-size:small"><div><b><font face="arial, sans-serif"><br></font></b></div><div><font face="arial, sans-serif"><b>Abstract:</b> 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. </font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">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.</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">Host: <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a></font></div><div><br></div><div><br></div><div><br></div><div><br></div></div><div><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div></div>