Title: PCPs and hardness of approximation: beyond NP
Speaker: Andrew Drucker, IAS
Date: Wednesday, November 7, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
The famous PCP Theorem gives a valuable alternative characterization of the complexity class NP, and implies that natural optimization problems are NP-hard even to approximately solve. What is less well known is that analogous characterizations and hardness results have been shown for a number of classes 'beyond NP,' such as AM and PSPACE. I will discuss the known results and techniques and highlight some questions for further study.