Tolerant Linearity Testing and Locally Testable Codes

DOI10.1007/978-3-642-03685-9_45MaRDI QIDQ3638907zbMATH OpenOpenAlexFDO

Authors Swastik Kopparty, Shubhangi Saraf

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_45

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• Some recent results on local testing of sparse linear codes
• Linearity testing in characteristic two
• Tight bounds for testing k-linearity
• Algebraic testing and weight distributions of codes.
• Tolerant versus intolerant testing for Boolean properties

Cited in

(12)

• Locally testable codes and PCPs of almost-linear length
• Local testing of lattices
• Some recent results on local testing of sparse linear codes
• scientific article; zbMATH DE number 7559095 (Why is no real title available?)
• Direct sum testing
• Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
• Locally Testable Codes Require Redundant Testers
• Approximating the distance to monotonicity of Boolean functions
• On approximability of satisfiable k-CSPs. III
• Sample-based distance-approximation for subsequence-freeness
• Testing versus estimation of graph properties, revisited
• Let's try to be more tolerant: on tolerant property testing and distance approximation (invited talk)

This page was built for publication: Tolerant Linearity Testing and Locally Testable Codes

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