A PCP characterization of AM

DOI10.1007/978-3-642-22006-7_49MaRDI QIDQ3012834zbMATH OpenOpenAlexFDO

Authors Andrew Drucker

Publication date 6 July 2011

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22006-7_49

zbMATH Keywords

Arthur-Merlin gamesaverage-case complexityPCPs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A PCP characterization of NP with optimal amortized query complexity
• The PCP theorem by gap amplification
• The PCP theorem by gap amplification
• STACS 2005
• Probabilistic checking of proofs

Cites work

• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
• Hardness amplification within NP
• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 1332658 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• Low-End Uniform Hardness versus Randomness Tradeoffs for AM
• On the complexity of approximating the VC dimension.
• On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy
• Proof verification and the hardness of approximation problems
• Random Debaters and the Hardness of Approximating Stochastic Functions
• Randomness in interactive proofs
• Randomness-efficient sampling within NC\(^{1}\)
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• The PCP theorem by gap amplification
• Uniform direct product theorems: simplified, optimized, and derandomized
• Using Nondeterminism to Amplify Hardness

Cited in

(4)

• A PCP theorem for interactive proofs and applications
• A toolbox for barriers on interactive oracle proofs
• Guidable local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture
• Two combinatorial MA-complete problems

This page was built for publication: A PCP characterization of AM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012834)