CSE Seminar or Event & Women in Computing|
Hard Problems in Hardness of Approximation: Sharp Thresholds, Parallel Repetition and Unique Games
Dana Moshkovitz Aaronson
Tuesday, April 14, 2015|
09:00am - 10:00am
Add to Google Calendar
About the Event
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.
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.
Open to: Public