Bounds on 2-Query Codeword Testing View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003

AUTHORS

Eli Ben-Sasson , Oded Goldreich , Madhu Sudan

ABSTRACT

We present upper bounds on the size of codes that are locally testable by querying only two input symbols. For linear codes, we show that any 2-locally testable code with minimal distance δn over any finite field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}$\end{document} cannot have more than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$|\mathbb{F}|^{3/\delta}$\end{document} codewords. This result holds even for testers with two-sided error. For general (non-linear) codes we obtain the exact same bounds on the code size as a function of the minimal distance, but our bounds apply only for binary alphabets and one-sided error testers (i.e. with perfect completeness). Our bounds are obtained by examining the graph induced by the set of possible pairs of queries made by a codeword tester on a given code. We also demonstrate the tightness of our upper bounds and the essential role of certain parameters. More... »

PAGES

216-227

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-45198-3_19

DOI

http://dx.doi.org/10.1007/978-3-540-45198-3_19

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Division of Engineering and Applied Sciences, Harvard University and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Division of Engineering and Applied Sciences, Harvard University and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA"
          ], 
          "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": "Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Goldreich", 
        "givenName": "Oded", 
        "id": "sg:person.012050724555.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012050724555.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Laboratory for Computer Science, Massachusetts Institute of Technology, 200 Technology Square, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Laboratory for Computer Science, Massachusetts Institute of Technology, 200 Technology Square, 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": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "We present upper bounds on the size of codes that are locally testable by querying only two input symbols. For linear codes, we show that any 2-locally testable code with minimal distance \u03b4n over any finite field \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathbb{F}$\\end{document} cannot have more than \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$|\\mathbb{F}|^{3/\\delta}$\\end{document} codewords. This result holds even for testers with two-sided error. For general (non-linear) codes we obtain the exact same bounds on the code size as a function of the minimal distance, but our bounds apply only for binary alphabets and one-sided error testers (i.e. with perfect completeness). Our bounds are obtained by examining the graph induced by the set of possible pairs of queries made by a codeword tester on a given code. We also demonstrate the tightness of our upper bounds and the essential role of certain parameters.", 
    "editor": [
      {
        "familyName": "Arora", 
        "givenName": "Sanjeev", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Sahai", 
        "givenName": "Amit", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-45198-3_19", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-40770-6", 
        "978-3-540-45198-3"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "essential role", 
      "role", 
      "testing", 
      "size", 
      "function", 
      "tightness", 
      "results", 
      "minimal distance", 
      "tester", 
      "possible pairs", 
      "pairs", 
      "certain parameters", 
      "parameters", 
      "code", 
      "field", 
      "error", 
      "distance", 
      "set", 
      "upper bounds", 
      "two-sided error", 
      "one-sided error tester", 
      "queries", 
      "bounds", 
      "size of codes", 
      "input symbols", 
      "symbols", 
      "linear codes", 
      "testable codes", 
      "\u0394n", 
      "finite field", 
      "codewords", 
      "same bounds", 
      "code size", 
      "binary alphabet", 
      "alphabet", 
      "graph", 
      "codeword testing", 
      "minimal distance \u03b4n", 
      "distance \u03b4n", 
      "exact same bounds", 
      "error testers", 
      "codeword testers"
    ], 
    "name": "Bounds on 2-Query Codeword Testing", 
    "pagination": "216-227", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029661203"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-45198-3_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-45198-3_19", 
      "https://app.dimensions.ai/details/publication/pub.1029661203"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:10", 
    "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_175.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-45198-3_19"
  }
]
 

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-45198-3_19'

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-45198-3_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-45198-3_19'

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-45198-3_19'


 

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

136 TRIPLES      23 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-45198-3_19 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N221575a6a5ca430b84c83a0a09846ea1
4 schema:datePublished 2003
5 schema:datePublishedReg 2003-01-01
6 schema:description We present upper bounds on the size of codes that are locally testable by querying only two input symbols. For linear codes, we show that any 2-locally testable code with minimal distance δn over any finite field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}$\end{document} cannot have more than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$|\mathbb{F}|^{3/\delta}$\end{document} codewords. This result holds even for testers with two-sided error. For general (non-linear) codes we obtain the exact same bounds on the code size as a function of the minimal distance, but our bounds apply only for binary alphabets and one-sided error testers (i.e. with perfect completeness). Our bounds are obtained by examining the graph induced by the set of possible pairs of queries made by a codeword tester on a given code. We also demonstrate the tightness of our upper bounds and the essential role of certain parameters.
7 schema:editor Nd17efb7c74814fabac44a3e6b3ae5314
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N5de1ee21616540c09f801c4555f08576
12 schema:keywords alphabet
13 binary alphabet
14 bounds
15 certain parameters
16 code
17 code size
18 codeword testers
19 codeword testing
20 codewords
21 distance
22 distance δn
23 error
24 error testers
25 essential role
26 exact same bounds
27 field
28 finite field
29 function
30 graph
31 input symbols
32 linear codes
33 minimal distance
34 minimal distance δn
35 one-sided error tester
36 pairs
37 parameters
38 possible pairs
39 queries
40 results
41 role
42 same bounds
43 set
44 size
45 size of codes
46 symbols
47 testable codes
48 tester
49 testing
50 tightness
51 two-sided error
52 upper bounds
53 Δn
54 schema:name Bounds on 2-Query Codeword Testing
55 schema:pagination 216-227
56 schema:productId N45799c68d61e40bd9b803b041eec6094
57 N7953fd3b7f204195b97c7205005b78bf
58 schema:publisher N5df008731ee144f797f3b662fe744420
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029661203
60 https://doi.org/10.1007/978-3-540-45198-3_19
61 schema:sdDatePublished 2022-01-01T19:10
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N8a4d298a7f26409280cc38a39f4827a2
64 schema:url https://doi.org/10.1007/978-3-540-45198-3_19
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N0f7acebe09004914896f2dc49d645ec5 rdf:first sg:person.014663420265.17
69 rdf:rest rdf:nil
70 N221575a6a5ca430b84c83a0a09846ea1 rdf:first sg:person.014331106007.34
71 rdf:rest Nfdc8ab76db2448d1bb9d331bc8c561b9
72 N255e3f09b5dc49528f7972dc0f96f718 schema:familyName Sahai
73 schema:givenName Amit
74 rdf:type schema:Person
75 N45799c68d61e40bd9b803b041eec6094 schema:name doi
76 schema:value 10.1007/978-3-540-45198-3_19
77 rdf:type schema:PropertyValue
78 N575ca279785847c6965cb35fb7dd5cb1 schema:familyName Jansen
79 schema:givenName Klaus
80 rdf:type schema:Person
81 N5de1ee21616540c09f801c4555f08576 schema:isbn 978-3-540-40770-6
82 978-3-540-45198-3
83 schema:name Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
84 rdf:type schema:Book
85 N5df008731ee144f797f3b662fe744420 schema:name Springer Nature
86 rdf:type schema:Organisation
87 N7953fd3b7f204195b97c7205005b78bf schema:name dimensions_id
88 schema:value pub.1029661203
89 rdf:type schema:PropertyValue
90 N877d85e03fbd444b8c0b20e79037c75f schema:familyName Rolim
91 schema:givenName José D. P.
92 rdf:type schema:Person
93 N88ab88a46446432eaab400649486da72 rdf:first N575ca279785847c6965cb35fb7dd5cb1
94 rdf:rest Na16b305a069445f2a1c6b71c0741e695
95 N8a4d298a7f26409280cc38a39f4827a2 schema:name Springer Nature - SN SciGraph project
96 rdf:type schema:Organization
97 N9d8c1956ecf34a3184e8c592f0f686c4 schema:familyName Arora
98 schema:givenName Sanjeev
99 rdf:type schema:Person
100 Na16b305a069445f2a1c6b71c0741e695 rdf:first N877d85e03fbd444b8c0b20e79037c75f
101 rdf:rest Nd85cdc70bbb34e17b07608dc83dc5517
102 Nd17efb7c74814fabac44a3e6b3ae5314 rdf:first N9d8c1956ecf34a3184e8c592f0f686c4
103 rdf:rest N88ab88a46446432eaab400649486da72
104 Nd85cdc70bbb34e17b07608dc83dc5517 rdf:first N255e3f09b5dc49528f7972dc0f96f718
105 rdf:rest rdf:nil
106 Nfdc8ab76db2448d1bb9d331bc8c561b9 rdf:first sg:person.012050724555.27
107 rdf:rest N0f7acebe09004914896f2dc49d645ec5
108 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
109 schema:name Mathematical Sciences
110 rdf:type schema:DefinedTerm
111 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
112 schema:name Pure Mathematics
113 rdf:type schema:DefinedTerm
114 sg:person.012050724555.27 schema:affiliation grid-institutes:grid.13992.30
115 schema:familyName Goldreich
116 schema:givenName Oded
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012050724555.27
118 rdf:type schema:Person
119 sg:person.014331106007.34 schema:affiliation grid-institutes:grid.116068.8
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:grid.116068.8 schema:alternateName Division of Engineering and Applied Sciences, Harvard University and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
130 Laboratory for Computer Science, Massachusetts Institute of Technology, 200 Technology Square, 02139, Cambridge, MA, USA
131 schema:name Division of Engineering and Applied Sciences, Harvard University and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
132 Laboratory for Computer Science, Massachusetts Institute of Technology, 200 Technology Square, 02139, Cambridge, MA, USA
133 rdf:type schema:Organization
134 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
135 schema:name Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
136 rdf:type schema:Organization
 




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


...