Hard Problems in Hardness of Approximation: Sharp Thresholds, Parallel Repetition and Unique Games

Many of the optimization problems of interest to humanity are NP-hard, and most computer scientists believe that they have no efficient algorithms. Focusing on approximation rather than exact optimization might extend the reach of algorithmic technique into the intractable. However, for many NP-hard problems approximating them better than aproblem-dependent threshold turns out to be NP-hard as well. Proving so rigorously is a difficult task, which — by a leap of thought — leads to fundamental questions about the nature of proofs and their verification.

In this talk I&#39ll discuss the phenomenon of sharp thresholds in approximability, namely how many approximation problemstransform instantly from efficiently solvable to exponentially hard as one focuses on a better approximation (joint work with Ran Raz). I&#39ll discuss two prover games and a new, incredibly simple, method (&#34fortification&#34) for analyzing their parallel repetition. Finally, I&#39ll discuss a recent candidate hard instance for unique games, which might lead to progress on the Unique Games Conjecture – one of the biggest open problems in approximability (joint work with Subhash Khot).
Dana Moshkovitz is an assistant professor of Computer Science at MIT.
Her research is in Theoretical Computer Science, and much of it focuses
on the limitations of approximation algorithms and probabilistic checking of proofs.

Dana did her PhD at the Weizmann Institute in Israel.
Her thesis co-won the Nessyahu Prize for best math PhD thesis in Israel in 2009,
and part of this work was awarded the FOCS 2008 Best paper.

Dana went on to spend a couple of years at Princeton University
and the Institute of Advanced Study before joining MIT in the end of 2010.
She is the recipient of MIT&#39s Jerome Saltzer teaching award.