A PCP Characterization of AM (Q3012834)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	A PCP Characterization of AM	scientific article

Statements

scholarly article

0 references

A PCP Characterization of AM (English)

0 references

0 references

Automata, Languages and Programming

0 references

publication date

6 July 2011

0 references

zbMATH Keywords

Arthur-Merlin games

0 references

PCPs

0 references

average-case complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-3-642-22006-7_49

0 references

Proof verification and the hardness of approximation problems

0 references

Randomness in interactive proofs

0 references

Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding

0 references

0 references

Random Debaters and the Hardness of Approximating Stochastic Functions

0 references

The PCP theorem by gap amplification

0 references

Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem

0 references

On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy

0 references

Randomness-efficient sampling within NC\(^{1}\)

0 references

Using Nondeterminism to Amplify Hardness

0 references

0 references

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized

0 references

0 references

On the complexity of approximating the VC dimension.

0 references

Hardness amplification within NP

0 references

Low-End Uniform Hardness versus Randomness Tradeoffs for AM

0 references

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/978-3-642-22006-7_49

0 references

Mathematics Subject Classification ID

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:3012834

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q3012834&oldid=35236362"