Some recent results on local testing of sparse linear codes

DOI10.1007/978-3-642-16367-8_26MaRDI QIDQ4933384zbMATH OpenOpenAlexFDO

Authors Swastik Kopparty, Shubhangi Saraf

Publication date 12 October 2010

Published in Property Testing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16367-8_26

zbMATH Keywords

error-correcting codeslist-decodingrandom codes

Mathematics Subject Classification ID

Randomized algorithms (68W20) Linear codes (general theory) (94B05) Decoding (94B35)

Recommendations

• Local list-decoding and testing of random linear codes from high error
• Local list-decoding and testing of random linear codes from high error
• Tolerant Linearity Testing and Locally Testable Codes
• Low Rate Is Insufficient for Local Testability
• Succinct Representation of Codes with Applications to Testing

Cites work

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 5485538 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 5485571 (Why is no real title available?)
• Improved low-degree testing and its applications
• Learning polynomials with queries: The highly noisy case
• Linearity testing in characteristic two
• Low-degree tests at large distances
• New direct-product testers and 2-query PCPs
• Noise-tolerant learning, the parity problem, and the statistical query model
• On spectra of BCH codes
• PAC learning with nasty noise.
• Property testing and its connection to learning and approximation
• Pseudorandom generators without the XOR lemma (extended abstract)
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Sub-constant error low degree test of almost-linear size
• Tolerant Linearity Testing and Locally Testable Codes
• Tolerant property testing and distance approximation

Cited in

(6)

• Local list-decoding and testing of random linear codes from high error
• Local list-decoding and testing of random linear codes from high error
• Data stream algorithms for codeword testing (extended abstract)
• Succinct Representation of Codes with Applications to Testing
• Tolerant Linearity Testing and Locally Testable Codes
• Succinct representation of codes with applications to testing

This page was built for publication: Some recent results on local testing of sparse linear codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933384)