Robust Locally Testable Codes and Products of Codes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Eli Ben-Sasson , Madhu Sudan

ABSTRACT

We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically checkable proofs, we introduce the notion of robust local testability of codes. We relate this notion to a product of codes introduced by Tanner, and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally, by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low-degree multivariate polynomials (which are a special case of tensor codes).Combining these two results gives us a generic construction of codes of inverse polynomial rate, that are testable with poly-logarithmically many queries. We note these locally testable tensor codes can be obtained from any linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes. More... »

PAGES

286-297

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-540-22894-3
978-3-540-27821-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-27821-4_26

DOI

http://dx.doi.org/10.1007/978-3-540-27821-4_26

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Radcliffe Institute for Advanced Study, 34 Concord Avenue, 02138, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Radcliffe Institute for Advanced Study, 34 Concord Avenue, 02138, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ben-Sasson", 
        "givenName": "Eli", 
        "id": "sg:person.014331106007.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014331106007.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT and Radcliffe IAS, The Stata Center Rm. G640, 32 Vassar Street, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT and Radcliffe IAS, The Stata Center Rm. G640, 32 Vassar Street, 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sudan", 
        "givenName": "Madhu", 
        "id": "sg:person.014663420265.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically checkable proofs, we introduce the notion of robust local testability of codes. We relate this notion to a product of codes introduced by Tanner, and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally, by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low-degree multivariate polynomials (which are a special case of tensor codes).Combining these two results gives us a generic construction of codes of inverse polynomial rate, that are testable with poly-logarithmically many queries. We note these locally testable tensor codes can be obtained from any linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes.", 
    "editor": [
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Khanna", 
        "givenName": "Sanjeev", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Ron", 
        "givenName": "Dana", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-27821-4_26", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-22894-3", 
        "978-3-540-27821-4"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "products of codes", 
      "error-correcting codes", 
      "low-degree multivariate polynomials", 
      "inverse polynomial rate", 
      "checkable proofs", 
      "generic construction", 
      "proof technique", 
      "testable codes", 
      "tensor codes", 
      "local testability", 
      "code", 
      "multivariate polynomials", 
      "testability", 
      "queries", 
      "best distance", 
      "algebraic properties", 
      "linear errors", 
      "notion", 
      "proof", 
      "error", 
      "Safra", 
      "technique", 
      "polynomial rate", 
      "words", 
      "results", 
      "context", 
      "construction", 
      "location", 
      "lemma", 
      "distance", 
      "polynomials", 
      "membership", 
      "previous results", 
      "variants", 
      "products", 
      "general results", 
      "tensor product", 
      "Raz", 
      "rate", 
      "properties", 
      "test", 
      "Tanner", 
      "investigation", 
      "robust local testability", 
      "simple composition lemma", 
      "composition lemma", 
      "testable tensor codes", 
      "Robust Locally Testable Codes", 
      "Locally Testable Codes"
    ], 
    "name": "Robust Locally Testable Codes and Products of Codes", 
    "pagination": "286-297", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1010246624"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-27821-4_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-27821-4_26", 
      "https://app.dimensions.ai/details/publication/pub.1010246624"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:22", 
    "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/chapter/chapter_382.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-27821-4_26"
  }
]
 

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/978-3-540-27821-4_26'

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/978-3-540-27821-4_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27821-4_26'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27821-4_26'


 

This table displays all metadata directly associated to this object as RDF triples.

134 TRIPLES      23 PREDICATES      75 URIs      68 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-27821-4_26 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Na08a35bd20034c6fba3ff46313d831e3
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically checkable proofs, we introduce the notion of robust local testability of codes. We relate this notion to a product of codes introduced by Tanner, and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally, by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low-degree multivariate polynomials (which are a special case of tensor codes).Combining these two results gives us a generic construction of codes of inverse polynomial rate, that are testable with poly-logarithmically many queries. We note these locally testable tensor codes can be obtained from any linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes.
7 schema:editor N28f425d82960436d96708416051ebefe
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ne725973fdf80429d89d58e2d9dc4a27f
12 schema:keywords Locally Testable Codes
13 Raz
14 Robust Locally Testable Codes
15 Safra
16 Tanner
17 algebraic properties
18 best distance
19 checkable proofs
20 code
21 composition lemma
22 construction
23 context
24 distance
25 error
26 error-correcting codes
27 general results
28 generic construction
29 inverse polynomial rate
30 investigation
31 lemma
32 linear errors
33 local testability
34 location
35 low-degree multivariate polynomials
36 membership
37 multivariate polynomials
38 notion
39 polynomial rate
40 polynomials
41 previous results
42 products
43 products of codes
44 proof
45 proof technique
46 properties
47 queries
48 rate
49 results
50 robust local testability
51 simple composition lemma
52 technique
53 tensor codes
54 tensor product
55 test
56 testability
57 testable codes
58 testable tensor codes
59 variants
60 words
61 schema:name Robust Locally Testable Codes and Products of Codes
62 schema:pagination 286-297
63 schema:productId N2e77448628264e72906d5429c528c19f
64 N644946fc00184f5f8bcbbe58e459c822
65 schema:publisher N7f88328bf28c4b42bd79ee402def4827
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010246624
67 https://doi.org/10.1007/978-3-540-27821-4_26
68 schema:sdDatePublished 2022-01-01T19:22
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher N882a40a5b79b44adaa1809c500e18614
71 schema:url https://doi.org/10.1007/978-3-540-27821-4_26
72 sgo:license sg:explorer/license/
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N0d009b3edcf04277a6f8e0f8620f5fb8 rdf:first N1f970c3a4ed74b31a41883f5e98d6af5
76 rdf:rest N1dd17089c2224d0298216333d3eb4def
77 N1dd17089c2224d0298216333d3eb4def rdf:first N460c686961f149189b1cd8d0485a3d34
78 rdf:rest N41bee184c0bd4dd59059a6ac37da25f4
79 N1f970c3a4ed74b31a41883f5e98d6af5 schema:familyName Khanna
80 schema:givenName Sanjeev
81 rdf:type schema:Person
82 N28f425d82960436d96708416051ebefe rdf:first N9f6bdb37db42437491334b369b130ed6
83 rdf:rest N0d009b3edcf04277a6f8e0f8620f5fb8
84 N2e77448628264e72906d5429c528c19f schema:name dimensions_id
85 schema:value pub.1010246624
86 rdf:type schema:PropertyValue
87 N41bee184c0bd4dd59059a6ac37da25f4 rdf:first N9559984cca204b5d9d6ba83f516f6d42
88 rdf:rest rdf:nil
89 N41e28f1803364e1b8b52aa4196573d91 rdf:first sg:person.014663420265.17
90 rdf:rest rdf:nil
91 N460c686961f149189b1cd8d0485a3d34 schema:familyName Rolim
92 schema:givenName José D. P.
93 rdf:type schema:Person
94 N644946fc00184f5f8bcbbe58e459c822 schema:name doi
95 schema:value 10.1007/978-3-540-27821-4_26
96 rdf:type schema:PropertyValue
97 N7f88328bf28c4b42bd79ee402def4827 schema:name Springer Nature
98 rdf:type schema:Organisation
99 N882a40a5b79b44adaa1809c500e18614 schema:name Springer Nature - SN SciGraph project
100 rdf:type schema:Organization
101 N9559984cca204b5d9d6ba83f516f6d42 schema:familyName Ron
102 schema:givenName Dana
103 rdf:type schema:Person
104 N9f6bdb37db42437491334b369b130ed6 schema:familyName Jansen
105 schema:givenName Klaus
106 rdf:type schema:Person
107 Na08a35bd20034c6fba3ff46313d831e3 rdf:first sg:person.014331106007.34
108 rdf:rest N41e28f1803364e1b8b52aa4196573d91
109 Ne725973fdf80429d89d58e2d9dc4a27f schema:isbn 978-3-540-22894-3
110 978-3-540-27821-4
111 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
112 rdf:type schema:Book
113 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
114 schema:name Information and Computing Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
117 schema:name Data Format
118 rdf:type schema:DefinedTerm
119 sg:person.014331106007.34 schema:affiliation grid-institutes:None
120 schema:familyName Ben-Sasson
121 schema:givenName Eli
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014331106007.34
123 rdf:type schema:Person
124 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
125 schema:familyName Sudan
126 schema:givenName Madhu
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
128 rdf:type schema:Person
129 grid-institutes:None schema:alternateName Radcliffe Institute for Advanced Study, 34 Concord Avenue, 02138, Cambridge, MA, USA
130 schema:name Radcliffe Institute for Advanced Study, 34 Concord Avenue, 02138, Cambridge, MA, USA
131 rdf:type schema:Organization
132 grid-institutes:grid.116068.8 schema:alternateName MIT and Radcliffe IAS, The Stata Center Rm. G640, 32 Vassar Street, 02139, Cambridge, MA, USA
133 schema:name MIT and Radcliffe IAS, The Stata Center Rm. G640, 32 Vassar Street, 02139, Cambridge, MA, USA
134 rdf:type schema:Organization
 




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


...