<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
        {font-family:"Cambria Math";
        panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0in;
        margin-bottom:.0001pt;
        font-size:11.0pt;
        font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
span.EmailStyle17
        {mso-style-type:personal-compose;
        font-family:"Calibri",sans-serif;
        color:windowtext;}
.MsoChpDefault
        {mso-style-type:export-only;
        font-family:"Calibri",sans-serif;}
@page WordSection1
        {size:8.5in 11.0in;
        margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
        {page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-family:"Arial",sans-serif;color:black'>Colloquium Speaker<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:"Arial",sans-serif;color:black'>Yin-Tat Lee, </span>Massachusetts Institute of Technology<span style='font-family:"Arial",sans-serif;color:black'> <o:p></o:p></span></p><p class=MsoNormal><span style='font-family:"Arial",sans-serif;color:black'>April 5th, 12:30pm<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:"Arial",sans-serif;color:black'>Computer Science 105<o:p></o:p></span></p><p class=MsoNormal><o:p>&nbsp;</o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Title: Faster algorithms for fundamental convex problems and their applications in combinatorial optimization<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>&nbsp;Abstract:<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Convex optimization has been studied extensively and is a prominent tool in various areas such as combinatorial optimization, data analysis, operations research, and scientific computing.&nbsp; Each field has developed specialized tools including data structures, sampling methods, and dimension reduction. In the past several years, I have been combining and improving the optimization techniques from different fields to design faster optimization algorithms.&nbsp;<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>&nbsp;In this talk, I will discuss my work in this direction and illustrate it through my results on linear programming and general convex optimization. In particular, I will present a new algorithm for solving linear programs, which gives the first improvement to the running time for linear programming in 25 years. Then, I will present the first nearly cubic time algorithm for solving general convex optimization problems. Furthermore, I will discuss how these two results can be used to improve the running time of many classical combinatorial problems such as maximum flow and submodular function minimization.<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>&nbsp;This talk will assume no prior knowledge of optimization.<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>&nbsp;Bio:<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Yin Tat Lee is a Ph.D. candidate in the department of mathematics at the Massachusetts Institute of Technology. He is interested in designing faster algorithms, particularly for problems in optimization. Since he began his Ph.D. in 2012, he has combined ideas from continuous and discrete mathematics to substantially advance the state-of-the-art for solving many fundamental problems in computer science, such as linear programming, maximum flow, and submodular function minimization. He has received a variety of awards, including the Best Student Paper Award at FOCS 2015, Best Paper Award at SODA 2014, Best Paper Award and Best Student Paper Award at FOCS 2014, and Notable Article in Computing in 2014 by Computing Reviews.<o:p></o:p></p><p class=MsoNormal><o:p>&nbsp;</o:p></p><p class=MsoNormal><o:p>&nbsp;</o:p></p><p class=MsoNormal>Mitra Kelly<o:p></o:p></p><p class=MsoNormal>Academic Secretary<o:p></o:p></p><p class=MsoNormal>Princeton University<o:p></o:p></p><p class=MsoNormal>Computer Science Dept<o:p></o:p></p><p class=MsoNormal>35 Olden Street<o:p></o:p></p><p class=MsoNormal>Princeton NJ 08540<o:p></o:p></p><p class=MsoNormal><a href="mailto:mkelly@cs.princeton.edu">mkelly@cs.princeton.edu</a><o:p></o:p></p><p class=MsoNormal>609-258-4562<o:p></o:p></p><p class=MsoNormal><o:p>&nbsp;</o:p></p></div></body></html>