[talks] Colloquium Speaker Yin-Tat Lee, TODAY April 5th- 12:30pm

[Mitra D. Kelly]

Colloquium Speaker

Yin-Tat Lee, Massachusetts Institute of Technology 

April 5th, 12:30pm

Computer Science 105

 

Title: Faster algorithms for fundamental convex problems and their
applications in combinatorial optimization

 Abstract:

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.  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. 

 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.

 This talk will assume no prior knowledge of optimization.

 Bio:

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.

 

 

Mitra Kelly

Academic Secretary

Princeton University

Computer Science Dept

35 Olden Street

Princeton NJ 08540

mkelly at cs.princeton.edu <mailto:mkelly at cs.princeton.edu> 

609-258-4562

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20160405/cbcbdfc3/attachment.html>