Yuan Zhou of Carnegie Mellon University will speak on "Understanding the Power of Convex Relaxation Hierarchies: Effectiveness and Limitations."
Optimization is a broad class of problems arising everywhere in
computer science, operations research, etc. Efficient algorithms that
approximate the optimal solution are desirable for many optimization
problems that seem computationally intractable. Convex programming
relaxation hierarchies have proven to be the most powerful tool to
design approximation algorithms for optimization problems.
In this talk, I will introduce convex relaxation hierarchies and
explain how to understand their computational power. Using several
fundamental optimization problems like Max-Cut, Sparsest-Cut, and
Max-Graph-Isomorphism as examples, I will illustrate:
1) how to design approximation algorithms via hierarchies,
2) how certain problems are resistant to hierarchies, and their significance, and
3) a surprising connection between hierarchies and the theory of
algebraic proof complexity.
In the end, I will propose directions to further explore the power of
convex relaxation hierarchies, which hopefully will lead to answer the
most important question in approximation algorithms research -- whether
the simplest semidefinite programming relaxation is optimal for many
Yuan Zhou is a graduate student at Carnegie Mellon University under
the supervision of Professors Venkatesan Guruswami and Ryan O'Donnell.
He received his bachelor's degree in computer science from Tsinghua
University in 2009, where he attended the Special Pilot CS Class
supervised by Turing Award laureate Professor Andrew Yao. He also
obtained his M.S. in computer science from Carnegie Mellon University
in 2013. Yuan was an intern at Microsoft Research Asia (2009), New
England (2011), Silicon Valley (2012) and Toyota Technological
Institute at Chicago (2010 and 2013). He was also a recipient of the
Simons Graduate Fellowships in theoretical computer science.
Yuan's research interests focus on approximability of fundamental
optimization problems. He also publishes work on other topics in
theoretical computer science, statistical machine learning, and
operations research, including analysis of Boolean functions,
algebraic dichotomy theory, algorithmic game theory, quantum
information theory, optimal learning for data analytics, and process
flexibility in supply chains.
Events are free and open to the public unless otherwise noted.