Output details
11 - Computer Science and Informatics
Birkbeck College
Article title
Sound 3-Query PCPPs Are Long
Type
D - Journal article
Title of journal
ACM Transactions on Computation Theory
Article number
-
Volume number
1
Issue number
2
First page of article
1
ISSN of journal
19423454
Year of publication
2009
URL
-
Number of additional authors
3
Additional information
<10> The PCP (probabilistic checkable proof) theorem is a central tool for proving the hardness of approximating computational problems (in 2001, Aurora et al. received the Goedel prize for initiating the study of PCP). A critical issue in applying the PCP theorem is the parameters for which it works. These parameters depend on specific PCP constructions. In this paper we have shown for the first time explicit constraints on the parameters of a key ingredient common to many PCP constructions.
Interdisciplinary
-
Cross-referral requested
-
Research group
A - Computational Intelligence
Citation count
5
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
