Small PCPs with low query complexity View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2000-12

AUTHORS

P. Harsha, M. Sudan

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... »

PAGES

157-201

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/pl00001606

DOI

http://dx.doi.org/10.1007/pl00001606

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1025900372


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

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": [
      "low query complexity", 
      "query complexity", 
      "proof size", 
      "high (though constant) query complexity", 
      "checkable proofs", 
      "large polynomials", 
      "new module", 
      "known constructions", 
      "complexity", 
      "PCP constructions", 
      "verifier", 
      "proof", 
      "correct proof", 
      "probability one", 
      "numerous components", 
      "bits", 
      "module", 
      "construction", 
      "false assertions", 
      "blowup", 
      "probability", 
      "assertion", 
      "polynomials", 
      "one", 
      "number", 
      "process", 
      "transformation", 
      "use", 
      "size", 
      "components", 
      "theorem", 
      "PCP", 
      "paper", 
      "super-cubic blowup", 
      "Small PCPs"
    ], 
    "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-01-01T18:11", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_344.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/pl00001606"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

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.

102 TRIPLES      21 PREDICATES      61 URIs      53 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 Ne31b1d914be4484eacf39648a58abd2e
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 N7f82491bd3684f19b4685b351ddc424b
11 Nda742820e3c14d8798b35c28f1b2f519
12 sg:journal.1136224
13 schema:keywords PCP
14 PCP constructions
15 Small PCPs
16 assertion
17 bits
18 blowup
19 checkable proofs
20 complexity
21 components
22 construction
23 correct proof
24 false assertions
25 high (though constant) query complexity
26 known constructions
27 large polynomials
28 low query complexity
29 module
30 new module
31 number
32 numerous components
33 one
34 paper
35 polynomials
36 probability
37 probability one
38 process
39 proof
40 proof size
41 query complexity
42 size
43 super-cubic blowup
44 theorem
45 transformation
46 use
47 verifier
48 schema:name Small PCPs with low query complexity
49 schema:pagination 157-201
50 schema:productId N3a9526e31e1b4896a8bb9a72cfefe856
51 Ne595bf64baa4462290c5d648a613dd1c
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025900372
53 https://doi.org/10.1007/pl00001606
54 schema:sdDatePublished 2022-01-01T18:11
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher Nf3c3cd2919274f0b95dc7f5bf2d51d79
57 schema:url https://doi.org/10.1007/pl00001606
58 sgo:license sg:explorer/license/
59 sgo:sdDataset articles
60 rdf:type schema:ScholarlyArticle
61 N3a9526e31e1b4896a8bb9a72cfefe856 schema:name dimensions_id
62 schema:value pub.1025900372
63 rdf:type schema:PropertyValue
64 N7f82491bd3684f19b4685b351ddc424b schema:issueNumber 3
65 rdf:type schema:PublicationIssue
66 Nda742820e3c14d8798b35c28f1b2f519 schema:volumeNumber 9
67 rdf:type schema:PublicationVolume
68 Ndaae2ce8936b4ddfa8126b4a833efb62 rdf:first sg:person.014663420265.17
69 rdf:rest rdf:nil
70 Ne31b1d914be4484eacf39648a58abd2e rdf:first sg:person.012210720000.77
71 rdf:rest Ndaae2ce8936b4ddfa8126b4a833efb62
72 Ne595bf64baa4462290c5d648a613dd1c schema:name doi
73 schema:value 10.1007/pl00001606
74 rdf:type schema:PropertyValue
75 Nf3c3cd2919274f0b95dc7f5bf2d51d79 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
78 schema:name Information and Computing Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
81 schema:name Computation Theory and Mathematics
82 rdf:type schema:DefinedTerm
83 sg:journal.1136224 schema:issn 1016-3328
84 1420-8954
85 schema:name computational complexity
86 schema:publisher Springer Nature
87 rdf:type schema:Periodical
88 sg:person.012210720000.77 schema:affiliation grid-institutes:grid.116068.8
89 schema:familyName Harsha
90 schema:givenName P.
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012210720000.77
92 rdf:type schema:Person
93 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
94 schema:familyName Sudan
95 schema:givenName M.
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
97 rdf:type schema:Person
98 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
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 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
101 Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, U.S.A., e-mail: prahladh@mit.edu, US
102 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...