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": [
      "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

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.

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
 




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


...