Name
Abstract | ||
|---|---|---|
The soundness error of a PCP verifier is the probability (usually denoted ε) that the verifier accepts an incorrect input. We are interested in the smallest possible values of ε for which the PCP theorem holds, and in particular whether the theorem holds when ε is an inverse polynomial function of the input length. We discuss the 'sliding scale conjecture' of [BGLR93, LY94] and related questions. We then sketch some of the existing approaches and constructions of PCPs with sub-constant soundness error. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1412700.1412713 | SIGACT News |
Keywords | Field | DocType |
input length,soundness error,pcp verifier,pcp theorem,existing approach,sub-constant soundness error,scale conjecture,incorrect input,small soundness error,related question,inverse polynomial function | Discrete mathematics,Inverse,Combinatorics,Polynomial,Sliding scale,Soundness,PCP theorem,Conjecture,Mathematics,Sketch | Journal |
Volume | Issue | Citations |
39 | 3 | 3 |
PageRank | References | Authors |
0.42 | 14 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Dinur | 1 | 1187 | 85.67 |