A PCP Characterization of AM
From MaRDI portal
Publication:3012834
DOI10.1007/978-3-642-22006-7_49zbMath1333.68117OpenAlexW1670983858MaRDI QIDQ3012834
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
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (2)
A PCP theorem for interactive proofs and applications ⋮ A toolbox for barriers on interactive oracle proofs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Randomness-efficient sampling within NC\(^{1}\)
- Randomness in interactive proofs
- 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
- Low-End Uniform Hardness versus Randomness Tradeoffs for AM
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
- Random Debaters and the Hardness of Approximating Stochastic Functions
- Using Nondeterminism to Amplify Hardness
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- The PCP theorem by gap amplification
- Hardness amplification within NP
This page was built for publication: A PCP Characterization of AM
