Loading...
Please wait, while we are loading the content...
Similar Documents
Lecture 9 : The PCP Theorem Via gap Amplification
| Content Provider | Semantic Scholar |
|---|---|
| Author | Moshkovitz, Dana |
| Copyright Year | 2011 |
| Abstract | We start by presenting a PCP system with two queries as a graph. The vertices correspond to locations of the proof. The edges correspond to tests made by the verifier on the two endpoints. Each vertex is assigned a symbol from an alphabet Σ by the prover. Each edge is associated with a constraint on pairs in Σ×Σ. Note that the definition of “degree” we had before coincides with the definition of the maximal degree in the graph. We consider the following gap problem: given a graph as above, distinguish between the following two cases: |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/9-gap-amplification.pdf |
| Alternate Webpage(s) | http://people.csail.mit.edu/dmoshkov//courses/pcp-mit/9-gap-amplification.pdf |
| Alternate Webpage(s) | http://www.cs.utexas.edu/~danama/courses/pcp-mit/9-gap-amplification.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
