Title: Recent Ideas in Approximation Algorithms and Hardness of Approximation
Date & Time: July 29 (Monday) 11AM
Location: E3-1 4443 (오상수 영상강의실)
Abstract:
For most of the important optimization problems we encounter, the successful theory of NP-hardness predicts that no polynomial-time algorithm finds the optimal solution exactly. Approximation algorithms, polynomial-time algorithms that find an approximate solution with some provable guarantee, provide the most natural alternatives. Proving that even an approximation is impossible beyond some threshold, known as hardness of approximation, is also an important area of computational complexity theory.

In this talk, starting from gentle introductions to approximation algorithms and hardness of approximation, I will discuss important recent ideas in the area, including semidefinite programming (SDP) and the use of real-stable polynomials from the algorithms side and the Unique Games Conjecture (UGC) from the hardness side. One underlying paradigm will be how the computational study of "discrete" optimization problems has interacted with more "continuous" branches of mathematics and operations research.

Bio:
Euiwoong Lee is an assistant professor at the University of Michigan. He got his Ph.D. from Carnegie Mellon University in 2017 and worked as a research fellow at the Simons Institute for the Theory of Computing at UC Berkeley and a postdoc at New York University. His research interests lie in several topics of theoretical computer science including approximation algorithms and hardness of approximation. His work has been recognized by several awards, including NSF CAREER Award, Edmund M. Clarke Dissertation Award, and ICALP Best Student Paper Award.