Some Recent Results on Local Testing of Sparse Linear Codes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Swastik Kopparty , Shubhangi Saraf

ABSTRACT

We study the local testability of linear codes. Our approach is based on a reformulation of this question in the language of tolerant linearity testing under a non-uniform distribution. We then study the question of linearity testing under non-uniform distributions directly, and give a sufficient criterion for linearity to be tolerantly testable under a given distribution. We show that several natural classes of distributions satisfy this criterion (such as product distributions and low Fourier-bias distributions), thus showing that linearity is tolerantly testable under these distributions. This in turn implies that the corresponding codes are locally testable.For the case of random sparse linear codes, we show the testability and decodability of such codes in the presence of very high noise rates. More precisely, we show that any linear code in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_2^n$\end{document} which is: sparse (i.e., has only poly(n) codewords)unbiased (i.e., each nonzero codeword has Hamming weight in (1/2 − n − γ, 1/2 + n − γ) for some constant γ> 0)can be locally tested and locally list decoded from (1/2 − ε)-fraction errors using only \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$poly(\frac{1}{\epsilon})$\end{document} queries to the received word. This simultaneously simplifies and strengthens a result of Kaufman and Sudan, who gave a local tester and local (unique) decoder for such codes from some constant fraction of errors. For the case of Dual BCH codes, our algorithms can also be made to run in sublinear time.Building on the methods used for the local algorithms, we also give sub-exponential time algorithms for list-decoding arbitrary unbiased (but not necessarily sparse) linear codes in the high-error regime. More... »

PAGES

320-333

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_26

DOI

http://dx.doi.org/10.1007/978-3-642-16367-8_26

DIMENSIONS

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


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": "Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kopparty", 
        "givenName": "Swastik", 
        "id": "sg:person.014276170447.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saraf", 
        "givenName": "Shubhangi", 
        "id": "sg:person.015177766032.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015177766032.20"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We study the local testability of linear codes. Our approach is based on a reformulation of this question in the language of tolerant linearity testing under a non-uniform distribution. We then study the question of linearity testing under non-uniform distributions directly, and give a sufficient criterion for linearity to be tolerantly testable under a given distribution. We show that several natural classes of distributions satisfy this criterion (such as product distributions and low Fourier-bias distributions), thus showing that linearity is tolerantly testable under these distributions. This in turn implies that the corresponding codes are locally testable.For the case of random sparse linear codes, we show the testability and decodability of such codes in the presence of very high noise rates. More precisely, we show that any linear code in \\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}_2^n$\\end{document} which is: \nsparse (i.e., has only poly(n) codewords)unbiased (i.e., each nonzero codeword has Hamming weight in (1/2\u2009\u2212\u2009n\u2009\u2212\u2009\u03b3, 1/2\u2009+\u2009n\u2009\u2212\u2009\u03b3) for some constant \u03b3>\u20090)can be locally tested and locally list decoded from (1/2\u2009\u2212\u2009\u03b5)-fraction errors using only \\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}$poly(\\frac{1}{\\epsilon})$\\end{document} queries to the received word. This simultaneously simplifies and strengthens a result of Kaufman and Sudan, who gave a local tester and local (unique) decoder for such codes from some constant fraction of errors. For the case of Dual BCH codes, our algorithms can also be made to run in sublinear time.Building on the methods used for the local algorithms, we also give sub-exponential time algorithms for list-decoding arbitrary unbiased (but not necessarily sparse) linear codes in the high-error regime.", 
    "editor": [
      {
        "familyName": "Goldreich", 
        "givenName": "Oded", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-16367-8_26", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-16366-1", 
        "978-3-642-16367-8"
      ], 
      "name": "Property Testing", 
      "type": "Book"
    }, 
    "keywords": [
      "linear codes", 
      "sparse linear codes", 
      "such codes", 
      "dual BCH codes", 
      "question of linearity", 
      "sufficient criteria", 
      "natural class", 
      "nonzero codewords", 
      "sublinear time", 
      "local algorithm", 
      "time algorithm", 
      "non-uniform distribution", 
      "corresponding code", 
      "BCH codes", 
      "algorithm", 
      "sub-exponential time algorithm", 
      "high-error regime", 
      "recent results", 
      "distribution", 
      "fraction errors", 
      "error", 
      "constant fraction", 
      "local testability", 
      "code", 
      "reformulation", 
      "class", 
      "decodability", 
      "noise rate", 
      "sparse", 
      "approach", 
      "linearity testing", 
      "criteria", 
      "cases", 
      "codewords", 
      "results", 
      "regime", 
      "linearity", 
      "high noise rates", 
      "Kaufman", 
      "local decoder", 
      "decoder", 
      "local testing", 
      "testability", 
      "questions", 
      "turn", 
      "time", 
      "testing", 
      "presence", 
      "rate", 
      "weight", 
      "list", 
      "fraction", 
      "language", 
      "words", 
      "tester", 
      "method", 
      "Sudan", 
      "local testers"
    ], 
    "name": "Some Recent Results on Local Testing of Sparse Linear Codes", 
    "pagination": "320-333", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037863833"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-16367-8_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-16367-8_26", 
      "https://app.dimensions.ai/details/publication/pub.1037863833"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:28", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_171.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-16367-8_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-642-16367-8_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-642-16367-8_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_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-642-16367-8_26'


 

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

125 TRIPLES      23 PREDICATES      84 URIs      77 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-16367-8_26 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N0ce894edbda64c22a7291155f466dbbf
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description We study the local testability of linear codes. Our approach is based on a reformulation of this question in the language of tolerant linearity testing under a non-uniform distribution. We then study the question of linearity testing under non-uniform distributions directly, and give a sufficient criterion for linearity to be tolerantly testable under a given distribution. We show that several natural classes of distributions satisfy this criterion (such as product distributions and low Fourier-bias distributions), thus showing that linearity is tolerantly testable under these distributions. This in turn implies that the corresponding codes are locally testable.For the case of random sparse linear codes, we show the testability and decodability of such codes in the presence of very high noise rates. More precisely, we show that any linear code in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_2^n$\end{document} which is: sparse (i.e., has only poly(n) codewords)unbiased (i.e., each nonzero codeword has Hamming weight in (1/2 − n − γ, 1/2 + n − γ) for some constant γ> 0)can be locally tested and locally list decoded from (1/2 − ε)-fraction errors using only \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$poly(\frac{1}{\epsilon})$\end{document} queries to the received word. This simultaneously simplifies and strengthens a result of Kaufman and Sudan, who gave a local tester and local (unique) decoder for such codes from some constant fraction of errors. For the case of Dual BCH codes, our algorithms can also be made to run in sublinear time.Building on the methods used for the local algorithms, we also give sub-exponential time algorithms for list-decoding arbitrary unbiased (but not necessarily sparse) linear codes in the high-error regime.
7 schema:editor Nfc08701a1f5848e0826097d6a1949568
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3141b5518cc84920b44e24da8c179712
12 schema:keywords BCH codes
13 Kaufman
14 Sudan
15 algorithm
16 approach
17 cases
18 class
19 code
20 codewords
21 constant fraction
22 corresponding code
23 criteria
24 decodability
25 decoder
26 distribution
27 dual BCH codes
28 error
29 fraction
30 fraction errors
31 high noise rates
32 high-error regime
33 language
34 linear codes
35 linearity
36 linearity testing
37 list
38 local algorithm
39 local decoder
40 local testability
41 local testers
42 local testing
43 method
44 natural class
45 noise rate
46 non-uniform distribution
47 nonzero codewords
48 presence
49 question of linearity
50 questions
51 rate
52 recent results
53 reformulation
54 regime
55 results
56 sparse
57 sparse linear codes
58 sub-exponential time algorithm
59 sublinear time
60 such codes
61 sufficient criteria
62 testability
63 tester
64 testing
65 time
66 time algorithm
67 turn
68 weight
69 words
70 schema:name Some Recent Results on Local Testing of Sparse Linear Codes
71 schema:pagination 320-333
72 schema:productId N8e3107647bf24d6bbcafb0bd8b775370
73 N91666510c8b34a988aea4c58faf54264
74 schema:publisher N13013fa8dd77405aaefead14cfa73d95
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037863833
76 https://doi.org/10.1007/978-3-642-16367-8_26
77 schema:sdDatePublished 2022-06-01T22:28
78 schema:sdLicense https://scigraph.springernature.com/explorer/license/
79 schema:sdPublisher N52c58f76a7d448009a1862e860fad6e5
80 schema:url https://doi.org/10.1007/978-3-642-16367-8_26
81 sgo:license sg:explorer/license/
82 sgo:sdDataset chapters
83 rdf:type schema:Chapter
84 N0ce894edbda64c22a7291155f466dbbf rdf:first sg:person.014276170447.16
85 rdf:rest N4d293c2dd11749ef92a93fb63399a5c5
86 N13013fa8dd77405aaefead14cfa73d95 schema:name Springer Nature
87 rdf:type schema:Organisation
88 N3141b5518cc84920b44e24da8c179712 schema:isbn 978-3-642-16366-1
89 978-3-642-16367-8
90 schema:name Property Testing
91 rdf:type schema:Book
92 N4d293c2dd11749ef92a93fb63399a5c5 rdf:first sg:person.015177766032.20
93 rdf:rest rdf:nil
94 N52c58f76a7d448009a1862e860fad6e5 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 N8e3107647bf24d6bbcafb0bd8b775370 schema:name dimensions_id
97 schema:value pub.1037863833
98 rdf:type schema:PropertyValue
99 N91666510c8b34a988aea4c58faf54264 schema:name doi
100 schema:value 10.1007/978-3-642-16367-8_26
101 rdf:type schema:PropertyValue
102 Ncc8010c60a6e49e28b4eb43e14e91dc9 schema:familyName Goldreich
103 schema:givenName Oded
104 rdf:type schema:Person
105 Nfc08701a1f5848e0826097d6a1949568 rdf:first Ncc8010c60a6e49e28b4eb43e14e91dc9
106 rdf:rest rdf:nil
107 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
108 schema:name Information and Computing Sciences
109 rdf:type schema:DefinedTerm
110 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
111 schema:name Data Format
112 rdf:type schema:DefinedTerm
113 sg:person.014276170447.16 schema:affiliation grid-institutes:grid.116068.8
114 schema:familyName Kopparty
115 schema:givenName Swastik
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16
117 rdf:type schema:Person
118 sg:person.015177766032.20 schema:affiliation grid-institutes:grid.116068.8
119 schema:familyName Saraf
120 schema:givenName Shubhangi
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015177766032.20
122 rdf:type schema:Person
123 grid-institutes:grid.116068.8 schema:alternateName Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, USA
124 schema:name Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, USA
125 rdf:type schema:Organization
 




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


...