Titile: Global geometric reductions for some bottleneck questions in hardness of approximation
|Affiliation:||University of Waterloo|
|Location:||MC 5501 or contact Eva Lee for Zoom link|
Abstract: I will describe the classical "local gadget reduction" paradigm for proving hardness of approximation results and then list some important optimization problems that resist all such attacks. With a focus on problems that can be cast as quadratic maximization over convex sets, I will describe some successes in bypassing the aforementioned bottleneck using ideas from geometry. Time permitting I will also describe some compelling new frontiers where answering some questions in convex geometry could be the path forward.