On November 12, 2018


이의웅 (NYU / PostDoc)


Bridging Continuous and Discrete Optimization Through the Lens of Approximation


Mathematical optimization is a field that studies algorithms, given an objective function and a feasible set, to find the element that maximizes or minimizes the objective function from the feasible set. While most interesting optimization problems are NP-hard and unlikely to admit efficient algorithms that find the exact optimal solution, many of them admit efficient "approximation algorithms" that find an approximate optimal solution.

Continuous and discrete optimization are the two main branches of mathematical optimization that have been primarily studied in different contexts. In this talk, I will introduce my recent results that bridge some of important continuous and discrete optimization problems, such as matrix low-rank approximation and Unique Games. At the heart of the connection is the problem of approximately computing the operator norm of a matrix with respect to various norms, which will allow us to borrow mathematical tools from functional analysis.


Euiwoong Lee is a postdoc at New York University hosted by Oded Regev and Subhash Khot, as part of the Simons Collaboration on Algorithms and Geometry. He was a research fellow at Simons Institute for the Theory of Computing, participating the Bridging Continuous and Discrete Optimization program. He received his PhD from Carnegie Mellon University in 2017, under the supervision of Prof Venkatesan Guruswami. His PhD thesis won the Edmund M. Clarke Doctoral Dissertation Award.