New Barriers to Optimization

Speaker:        Dr. Siu-On CHAN
                Microsoft Research

Title:          "New Barriers to Optimization"

Date:           Thursday, 12 March 2015

Time:           11:00am - 12 noon

Venue:          Lecture Theatre H (near lifts 27/28), HKUST

Abstract:

Powerful optimization algorithms have led to impressive results over the 
past decades. At the same time, their limitations have emerged. Such 
limitations are typically NP-hardness results or hard instances for a 
particular convex relaxation. In this talk, I will discuss the interplay 
between these two kinds of limitations, and what new results may be 
discovered by looking at these limitations side by side. Central to these 
hardness results will be the approximability of constraint satisfaction 
problems.

Numerous such NP-hardness results rely on a complexity assumption, known as 
the Unique-Games Conjecture. The belief in this conjecture is somewhat 
shaken in light of recent advances. I will show that new or 
yet-to-be-discovered algorithms still fall short of better approximation 
guarantees for many optimization problems, regardless of the conjecture. 
Our main technical tool draws inspiration from well-known results in 
circuit complexity and communication complexity.

********************
Biography:

Siu On Chan is a Postdoc at Microsoft Research. He completed his PhD at UC
Berkeley and was advised by Luca Trevisan and Elchanan Mossel. He also did
his undergrad in Chinese University of Hong Kong and MSc at University of
Toronto earlier. He is interested in studying the fundamental limitations
of approximation algorithms, in particular convex optimization algorithms.
He is also interested in random graphs, testing and learning. He received
Best Paper Award and Best Student Paper Award at STOC 2013.