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:

• Condon, Feigenbaum, Lund, Shor '95: Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions.
• Drucker '11: Efficient Probabilistically Checkable Debates. (See also the references therein.)

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