Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Dana Moshkovitz

LFCS Seminar: Dana Moshkovitz

Projection Games

What
When Jul 13, 2012
from 02:00 PM to 03:00 PM
Where IF 4.31-4.33
Add event to calendar vCal
iCal


For the last couple of decades, projection PCPs are the basis of most  optimal NP-hardness of approximation results (PCP=Probabilistically Checkable Proofs). In this talk I will describe what projection games are, how they are used to derive hardness results, how unique games relate to them, and what are the main constructions and open questions. I'll also discuss a few recent results related to projection PCPs.

Document Actions