PCPs and Inapproximability: Recent Milestones, and New and Continuing Challenges
Sep 28, 2011
ABSTRACT:
Probabilistic proof checking and its connection to approximability of optimization problems celebrates its 20th birthday this year.
This talk will survey some key developments from the last decade in probabilistically checkable proofs (PCPs) and their applications to hardness of approximation results. We will also touch upon some of the now classic material from the first ten years of PCP research to set the background and context for our discussion.