Seminar Series by Nisheeth Vishnoi
Algorithms versus Hardness
Nisheeth Vishnoi
Microsoft Research Labs, Bangalore
Wednesday, May 26, 10 am to 12 noon : Introduction and Overview (Change of venue : CS101)
Wednesday, May 26, 2:30pm to 4:30 pm : Algorithms (Change of venue : CS101)
Thursday, May 27, 10 am : Hardness (Change of venue : CS101)
Friday, May 28, 10 am : Geometry (Change of venue : CS101)
Saturday, May 29, 10am : Duality (Change of venue : CS101)
Venue for all lectures : CS101 Abstract:
This talk will be concerned with how well can we approximate NP-hard problems. One of the most successful algorithmic strategies, from an upper bound perspective, is to write a tractable relaxation for an NP-hard problem and present a "rounding" algorithm. To prove a hardness of approximation result, on the other hand, one often gives a reduction assuming existence of computationally hard structures, for instance those promised by the conjecture $P \neq NP$.
Until recently, these seemed to be two different facets of a problem. This distinction is now blurring: we are beginning to understand systematic recipes of how to use the output of algorithmic relaxations to come up with reductions, and how to use the analysis of the hardness reduction to produce a rounding algorithm for the relaxation itself.
This viewpoint has led to the discovery of new and optimal algorithms and reductions for several important problems such as Max-Cut, Vertex Cover and beyond for which elegant and clever, but seemingly unrelated, algorithms and reductions were previously known, and seems to point to a promising future for approximability.
This talk should be acessible to and an attempt to explain this emerging duality between algorithms and complexity. The introductory talk will be followed up by the following 2hr lectures.
Lecture 1:Algorithms
SDP based for Max-Cut [Goemans,Williamson], LP based for Vertex Cover, Sparsest Cut [Arora,Rao,Vazirani] (statement)
Lecture 2: Hardness
PCP Theorem (statement), Label Cover, Parallel Repetition, Unique Games Conjecture, Dictatorship Tests
Lecture 3: Geometry
From UG-hardness to gap instances [Khot,Vishnoi] Invariance Principle [Mossel, O'Donnell, Oleskiewiscz]
Lecture 4: Duality
From gap instances to UG-hardness to rounding: Settling approximability of large class of Constraint Satisfaction Problems. [Raghavendra] &[Kumar,Manokaran,Tulsiani, Vishnoi]
Conclusion and Future Directions