Some recent results on local testing of sparse linear codes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 F2n 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 poly(1/ε) 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.

Original languageEnglish (US)
Title of host publicationProperty Testing - Current Research and Surveys
Pages320-333
Number of pages14
DOIs
StatePublished - Nov 24 2010
Externally publishedYes
EventMini-Workshop on Property Testing - Beijing, China
Duration: Jan 8 2010Jan 10 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6390 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherMini-Workshop on Property Testing
CountryChina
CityBeijing
Period1/8/101/10/10

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • error correcting codes
  • list-decoding
  • random codes

Cite this

Kopparty, S., & Saraf, S. (2010). Some recent results on local testing of sparse linear codes. In Property Testing - Current Research and Surveys (pp. 320-333). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6390 LNCS). https://doi.org/10.1007/978-3-642-16367-8_26