A PCP Characterization of AM

Optimization, approximation, and complexity classes

Christos H. Papadimitriou and Mihalis Yannakakis · 1991

Earlier work this paper cites.

Randomness in interactive proofs

Mihir Bellare, Oded Goldreich, and Shafi Goldwasser · 1993

Earlier work this paper cites.

Non-approximability in the polynomial-time hierarchy

Ker-I Ko and Chih-Long Lin · 1994

Earlier work this paper cites.

Computational Complexity

Christos H. Papadimitriou · 1994

Earlier work this paper cites.

Probabilistically checkable debate systems and nonapproximability of pspace-hard functions

Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter W. Shor · 1995

Earlier work this paper cites.

Hard-core distributions for somewhat hard problems

Russell Impagliazzo · 1995

Earlier work this paper cites.

Random debaters and the hardness of approximating stochastic functions

Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter W. Shor · 1997

Earlier work this paper cites.

Proof verification and the hardness of approximation problems

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy · 1998

Earlier work this paper cites.

Hard sets and pseudo-random generators for constant depth circuits

Manindra Agrawal · 2001

Earlier work this paper cites.

On the complexity of approximating the VC dimension

Elchanan Mossel and Christopher Umans · 2002

Cited alongside, same era.

Hardness amplification within NP

Ryan O’Donnell · 2002

Cited alongside, same era.

A randomness-efficient sampler for matrix-valued functions and applications

Avi Wigderson and David Xiao · 2005

Cited alongside, same era.

Robust PCPs of proximity, shorter PCPs, and applications to coding

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan · 2006

Cited alongside, same era.

Assignment testers: Towards a combinatorial proof of the PCP theorem

Irit Dinur and Omer Reingold · 2006

Cited alongside, same era.

Using nondeterminism to amplify hardness

Alexander Healy, Salil P. Vadhan, and Emanuele Viola · 2006

Cited alongside, same era.

Low-end uniform hardness vs. randomness tradeoffs for AM

Ronen Shaltiel and Christopher Umans · 2007

Later among the works it cites.

Sound 3-query PCPPs are long

Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, and Arie Matsliah · 2008

Later among the works it cites.

A (de)constructive approach to program checking

Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum · 2008

Later among the works it cites.

Randomness-efficient sampling within NC 1 {}^{\mbox{1}}

Alexander Healy · 2008

Later among the works it cites.

Uniform direct product theorems: simplified, optimized, and derandomized

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson · 2008

Later among the works it cites.

Hardness amplification proofs require majority

Ronen Shaltiel and Emanuele Viola · 2008

Later among the works it cites.