### 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