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": [
      "upper bounds", 
      "size of codes", 
      "finite field", 
      "bounds", 
      "linear codes", 
      "same bounds", 
      "two-sided error", 
      "one-sided error tester", 
      "certain parameters", 
      "minimal distance", 
      "input symbols", 
      "binary alphabet", 
      "code", 
      "testable codes", 
      "graph", 
      "possible pairs", 
      "field", 
      "error", 
      "\u0394n", 
      "codewords", 
      "code size", 
      "set", 
      "parameters", 
      "function", 
      "alphabet", 
      "size", 
      "symbols", 
      "distance", 
      "tightness", 
      "results", 
      "pairs", 
      "essential role", 
      "queries", 
      "testing", 
      "tester", 
      "role"
    ], 
    "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-05-20T07:43", 
    "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/chapter/chapter_198.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.

130 TRIPLES      23 PREDICATES      62 URIs      55 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 N35a5a15b673d407799bb452959383bf0
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 Nd68f2ff37eaf4df7a01768cadb1a4bda
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N4c24bed2df544999a03e8752c2b1ba38
12 schema:keywords alphabet
13 binary alphabet
14 bounds
15 certain parameters
16 code
17 code size
18 codewords
19 distance
20 error
21 essential role
22 field
23 finite field
24 function
25 graph
26 input symbols
27 linear codes
28 minimal distance
29 one-sided error tester
30 pairs
31 parameters
32 possible pairs
33 queries
34 results
35 role
36 same bounds
37 set
38 size
39 size of codes
40 symbols
41 testable codes
42 tester
43 testing
44 tightness
45 two-sided error
46 upper bounds
47 Δn
48 schema:name Bounds on 2-Query Codeword Testing
49 schema:pagination 216-227
50 schema:productId N039378c3e3b4430ba1eeec68edfd3c40
51 N75587d0c056a4fd39cfb24aba7bc1eb0
52 schema:publisher Ne7765d21ce104d4c8fa3a8693e16b4be
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029661203
54 https://doi.org/10.1007/978-3-540-45198-3_19
55 schema:sdDatePublished 2022-05-20T07:43
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher N619cd8857ee74847a892108f97d13438
58 schema:url https://doi.org/10.1007/978-3-540-45198-3_19
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N039378c3e3b4430ba1eeec68edfd3c40 schema:name doi
63 schema:value 10.1007/978-3-540-45198-3_19
64 rdf:type schema:PropertyValue
65 N18cf0ef949c445cfa3ba0be4f40b2699 schema:familyName Arora
66 schema:givenName Sanjeev
67 rdf:type schema:Person
68 N35a5a15b673d407799bb452959383bf0 rdf:first sg:person.014331106007.34
69 rdf:rest Ncb64cb58c18742a99b06bdf8a3bafc80
70 N465809d13d3540ab8ae385147261a61b rdf:first sg:person.014663420265.17
71 rdf:rest rdf:nil
72 N4b17bbb3507a4c8183ad78b11922bb5b rdf:first Nb678e1e0b6e94540ae7e008917c1d725
73 rdf:rest N54b5fdded23045318166489bda773ccb
74 N4c24bed2df544999a03e8752c2b1ba38 schema:isbn 978-3-540-40770-6
75 978-3-540-45198-3
76 schema:name Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
77 rdf:type schema:Book
78 N54b5fdded23045318166489bda773ccb rdf:first Ndc6613fcfe54461fbca4089f54e90d7d
79 rdf:rest Na85b1454c9fb478c96eb0ea8309ec6b0
80 N5cdee4d5610343488cdf524ba89b1dbb schema:familyName Sahai
81 schema:givenName Amit
82 rdf:type schema:Person
83 N619cd8857ee74847a892108f97d13438 schema:name Springer Nature - SN SciGraph project
84 rdf:type schema:Organization
85 N75587d0c056a4fd39cfb24aba7bc1eb0 schema:name dimensions_id
86 schema:value pub.1029661203
87 rdf:type schema:PropertyValue
88 Na85b1454c9fb478c96eb0ea8309ec6b0 rdf:first N5cdee4d5610343488cdf524ba89b1dbb
89 rdf:rest rdf:nil
90 Nb678e1e0b6e94540ae7e008917c1d725 schema:familyName Jansen
91 schema:givenName Klaus
92 rdf:type schema:Person
93 Ncb64cb58c18742a99b06bdf8a3bafc80 rdf:first sg:person.012050724555.27
94 rdf:rest N465809d13d3540ab8ae385147261a61b
95 Nd68f2ff37eaf4df7a01768cadb1a4bda rdf:first N18cf0ef949c445cfa3ba0be4f40b2699
96 rdf:rest N4b17bbb3507a4c8183ad78b11922bb5b
97 Ndc6613fcfe54461fbca4089f54e90d7d schema:familyName Rolim
98 schema:givenName José D. P.
99 rdf:type schema:Person
100 Ne7765d21ce104d4c8fa3a8693e16b4be schema:name Springer Nature
101 rdf:type schema:Organisation
102 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
103 schema:name Mathematical Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
106 schema:name Pure Mathematics
107 rdf:type schema:DefinedTerm
108 sg:person.012050724555.27 schema:affiliation grid-institutes:grid.13992.30
109 schema:familyName Goldreich
110 schema:givenName Oded
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012050724555.27
112 rdf:type schema:Person
113 sg:person.014331106007.34 schema:affiliation grid-institutes:grid.116068.8
114 schema:familyName Ben-Sasson
115 schema:givenName Eli
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014331106007.34
117 rdf:type schema:Person
118 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
119 schema:familyName Sudan
120 schema:givenName Madhu
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
122 rdf:type schema:Person
123 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
124 Laboratory for Computer Science, Massachusetts Institute of Technology, 200 Technology Square, 02139, Cambridge, MA, USA
125 schema:name Division of Engineering and Applied Sciences, Harvard University and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
126 Laboratory for Computer Science, Massachusetts Institute of Technology, 200 Technology Square, 02139, Cambridge, MA, USA
127 rdf:type schema:Organization
128 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
129 schema:name Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
130 rdf:type schema:Organization
 




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


...