Ontology type: schema:ScholarlyArticle Open Access: True
2000-12
AUTHORS ABSTRACT. Most known constructions of probabilistically checkable proofs (PCPs) either blow up the proof size by a large polynomial, or have a high (though constant) query complexity. In this paper we give a transformation with slightly-super-cubic blowup in proof size, with a low query complexity. Specifically, the verifier probes the proof in 16 bits and rejects every proof of a false assertion with probability arbitrarily close to 1/2, while accepting correct proofs of theorems with probability one. The proof is obtained by revisiting known constructions and improving numerous components therein. In the process we abstract a number of new modules that may be of use in other PCP constructions. More... »
PAGES157-201
http://scigraph.springernature.com/pub.10.1007/pl00001606
DOIhttp://dx.doi.org/10.1007/pl00001606
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1025900372
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, U.S.A., e-mail: prahladh@mit.edu, US",
"id": "http://www.grid.ac/institutes/grid.116068.8",
"name": [
"Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, U.S.A., e-mail: prahladh@mit.edu, US"
],
"type": "Organization"
},
"familyName": "Harsha",
"givenName": "P.",
"id": "sg:person.012210720000.77",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012210720000.77"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, U.S.A., e-mail: madhu@mit.edu, http://theory.lcs.mit.edu/~madhu/, US",
"id": "http://www.grid.ac/institutes/grid.116068.8",
"name": [
"Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, U.S.A., e-mail: madhu@mit.edu, http://theory.lcs.mit.edu/~madhu/, US"
],
"type": "Organization"
},
"familyName": "Sudan",
"givenName": "M.",
"id": "sg:person.014663420265.17",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
],
"type": "Person"
}
],
"datePublished": "2000-12",
"datePublishedReg": "2000-12-01",
"description": "Abstract. Most known constructions of probabilistically checkable proofs (PCPs) either blow up the proof size by a large polynomial, or have a high (though constant) query complexity. In this paper we give a transformation with slightly-super-cubic blowup in proof size, with a low query complexity. Specifically, the verifier probes the proof in 16 bits and rejects every proof of a false assertion with probability arbitrarily close to 1/2, while accepting correct proofs of theorems with probability one. The proof is obtained by revisiting known constructions and improving numerous components therein. In the process we abstract a number of new modules that may be of use in other PCP constructions.",
"genre": "article",
"id": "sg:pub.10.1007/pl00001606",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1136224",
"issn": [
"1016-3328",
"1420-8954"
],
"name": "computational complexity",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "9"
}
],
"keywords": [
"query complexity",
"probability one",
"large polynomials",
"known constructions",
"correct proof",
"high query complexity",
"proof",
"low query complexity",
"PCP constructions",
"complexity",
"theorem",
"proof size",
"polynomials",
"blowup",
"checkable proofs",
"construction",
"probability",
"false assertions",
"new module",
"numerous components",
"transformation",
"one",
"size",
"number",
"verifier",
"bits",
"module",
"process",
"components",
"assertion",
"use",
"PCP",
"paper"
],
"name": "Small PCPs with low query complexity",
"pagination": "157-201",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1025900372"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/pl00001606"
]
}
],
"sameAs": [
"https://doi.org/10.1007/pl00001606",
"https://app.dimensions.ai/details/publication/pub.1025900372"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:21",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_318.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/pl00001606"
}
]
Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/pl00001606'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/pl00001606'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/pl00001606'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/pl00001606'
This table displays all metadata directly associated to this object as RDF triples.
100 TRIPLES
21 PREDICATES
59 URIs
51 LITERALS
6 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/pl00001606 | schema:about | anzsrc-for:08 |
2 | ″ | ″ | anzsrc-for:0802 |
3 | ″ | schema:author | Na64d9f8bfe924db195ce36759fbfbdc1 |
4 | ″ | schema:datePublished | 2000-12 |
5 | ″ | schema:datePublishedReg | 2000-12-01 |
6 | ″ | schema:description | Abstract. Most known constructions of probabilistically checkable proofs (PCPs) either blow up the proof size by a large polynomial, or have a high (though constant) query complexity. In this paper we give a transformation with slightly-super-cubic blowup in proof size, with a low query complexity. Specifically, the verifier probes the proof in 16 bits and rejects every proof of a false assertion with probability arbitrarily close to 1/2, while accepting correct proofs of theorems with probability one. The proof is obtained by revisiting known constructions and improving numerous components therein. In the process we abstract a number of new modules that may be of use in other PCP constructions. |
7 | ″ | schema:genre | article |
8 | ″ | schema:inLanguage | en |
9 | ″ | schema:isAccessibleForFree | true |
10 | ″ | schema:isPartOf | N87831c25fcaf4b438cadc2f7b2c64c94 |
11 | ″ | ″ | Nc6f571ee1625406bb7b09f24b8fe0a71 |
12 | ″ | ″ | sg:journal.1136224 |
13 | ″ | schema:keywords | PCP |
14 | ″ | ″ | PCP constructions |
15 | ″ | ″ | assertion |
16 | ″ | ″ | bits |
17 | ″ | ″ | blowup |
18 | ″ | ″ | checkable proofs |
19 | ″ | ″ | complexity |
20 | ″ | ″ | components |
21 | ″ | ″ | construction |
22 | ″ | ″ | correct proof |
23 | ″ | ″ | false assertions |
24 | ″ | ″ | high query complexity |
25 | ″ | ″ | known constructions |
26 | ″ | ″ | large polynomials |
27 | ″ | ″ | low query complexity |
28 | ″ | ″ | module |
29 | ″ | ″ | new module |
30 | ″ | ″ | number |
31 | ″ | ″ | numerous components |
32 | ″ | ″ | one |
33 | ″ | ″ | paper |
34 | ″ | ″ | polynomials |
35 | ″ | ″ | probability |
36 | ″ | ″ | probability one |
37 | ″ | ″ | process |
38 | ″ | ″ | proof |
39 | ″ | ″ | proof size |
40 | ″ | ″ | query complexity |
41 | ″ | ″ | size |
42 | ″ | ″ | theorem |
43 | ″ | ″ | transformation |
44 | ″ | ″ | use |
45 | ″ | ″ | verifier |
46 | ″ | schema:name | Small PCPs with low query complexity |
47 | ″ | schema:pagination | 157-201 |
48 | ″ | schema:productId | N5a32b77acb6f4aedac81897a9cf144e7 |
49 | ″ | ″ | Nc1de541fb1ef4b8fb0f2feb3d7479d77 |
50 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1025900372 |
51 | ″ | ″ | https://doi.org/10.1007/pl00001606 |
52 | ″ | schema:sdDatePublished | 2022-05-20T07:21 |
53 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
54 | ″ | schema:sdPublisher | N9d3545a9be5e4c5ba33a3808793628d9 |
55 | ″ | schema:url | https://doi.org/10.1007/pl00001606 |
56 | ″ | sgo:license | sg:explorer/license/ |
57 | ″ | sgo:sdDataset | articles |
58 | ″ | rdf:type | schema:ScholarlyArticle |
59 | N5a32b77acb6f4aedac81897a9cf144e7 | schema:name | dimensions_id |
60 | ″ | schema:value | pub.1025900372 |
61 | ″ | rdf:type | schema:PropertyValue |
62 | N87831c25fcaf4b438cadc2f7b2c64c94 | schema:issueNumber | 3 |
63 | ″ | rdf:type | schema:PublicationIssue |
64 | N9d3545a9be5e4c5ba33a3808793628d9 | schema:name | Springer Nature - SN SciGraph project |
65 | ″ | rdf:type | schema:Organization |
66 | Na64d9f8bfe924db195ce36759fbfbdc1 | rdf:first | sg:person.012210720000.77 |
67 | ″ | rdf:rest | Na987fad15a99427882c2294e0e2fb5a6 |
68 | Na987fad15a99427882c2294e0e2fb5a6 | rdf:first | sg:person.014663420265.17 |
69 | ″ | rdf:rest | rdf:nil |
70 | Nc1de541fb1ef4b8fb0f2feb3d7479d77 | schema:name | doi |
71 | ″ | schema:value | 10.1007/pl00001606 |
72 | ″ | rdf:type | schema:PropertyValue |
73 | Nc6f571ee1625406bb7b09f24b8fe0a71 | schema:volumeNumber | 9 |
74 | ″ | rdf:type | schema:PublicationVolume |
75 | anzsrc-for:08 | schema:inDefinedTermSet | anzsrc-for: |
76 | ″ | schema:name | Information and Computing Sciences |
77 | ″ | rdf:type | schema:DefinedTerm |
78 | anzsrc-for:0802 | schema:inDefinedTermSet | anzsrc-for: |
79 | ″ | schema:name | Computation Theory and Mathematics |
80 | ″ | rdf:type | schema:DefinedTerm |
81 | sg:journal.1136224 | schema:issn | 1016-3328 |
82 | ″ | ″ | 1420-8954 |
83 | ″ | schema:name | computational complexity |
84 | ″ | schema:publisher | Springer Nature |
85 | ″ | rdf:type | schema:Periodical |
86 | sg:person.012210720000.77 | schema:affiliation | grid-institutes:grid.116068.8 |
87 | ″ | schema:familyName | Harsha |
88 | ″ | schema:givenName | P. |
89 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012210720000.77 |
90 | ″ | rdf:type | schema:Person |
91 | sg:person.014663420265.17 | schema:affiliation | grid-institutes:grid.116068.8 |
92 | ″ | schema:familyName | Sudan |
93 | ″ | schema:givenName | M. |
94 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17 |
95 | ″ | rdf:type | schema:Person |
96 | grid-institutes:grid.116068.8 | schema:alternateName | Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, U.S.A., e-mail: madhu@mit.edu, http://theory.lcs.mit.edu/~madhu/, US |
97 | ″ | ″ | Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, U.S.A., e-mail: prahladh@mit.edu, US |
98 | ″ | schema:name | Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, U.S.A., e-mail: madhu@mit.edu, http://theory.lcs.mit.edu/~madhu/, US |
99 | ″ | ″ | Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, U.S.A., e-mail: prahladh@mit.edu, US |
100 | ″ | rdf:type | schema:Organization |