DIMACS Theoretical Computer Science Seminar


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


Abstract:

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.

References:

See: http://paul.rutgers.edu/~yixinxu/theory-fall12.html