Towards a Unified Theory of Approximate Optimization

The theory of approximate optimization faces new challenges and opportunities thanks to its increasing interaction with other fields of optimization. Such growth and diversity call for a unified theory of approximate optimization, where various algorithms and complexity results can be connected to one another and explained by a few general principles. My research aims to contribute to such a theory, by building a unified theory for general classes of optimization problems and exploring connections between such classes. This talk will showcase results in both directions.

1. For the class of graph cut problems, I will present a general framework for proving optimal hardness results for many directed cut problems. I will also show my recent algorithmic results that improve long-standing barriers for the k-cut problem in various settings.

2. Finally, I will introduce some recently discovered connections between continuous and discrete optimization. These connections involve well-studied problems in the respective fields including low-rank approximation, operator norms, and small set expansion.
Euiwoong Lee is a postdoc at the Computer Science Department of New York University hosted by Oded Regev and Subhash Khot. He received his PhD in Computer Science from Carnegie Mellon University under the supervision of Venkat Guruswami. His research interests include topics in optimization algorithms and complexity theory, such as approximation algorithms, hardness of approximation, sum-of-squares hierarchies, and parameterized algorithms. He is a recipient of Edmund M. Clarke Doctoral Dissertation Award, ICALP Best Student Paper Award, and Simons Award for Graduate Students in Theoretical Computer Science.