Special Colloquium
Euiwoong Lee
NYU
Towards a unified theory of approximate optimization
Abstract: 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.
Colloquium tea to follow at 4PM in SEO 300.
Monday February 18, 2019 at 3:00 PM in 636 SEO