Limits on the Rate of Locally Testable Affine-Invariant Codes

DOI10.1007/978-3-642-22935-0_35zbMath1343.68288OpenAlexW2161560216MaRDI QIDQ3088114

Madhu Sudan, Eli Ben-Sasson

Publication date: 17 August 2011

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-22935-0_35

zbMATH Keywords

direct sumssymmetrieserror-correcting codesproperty testing

Mathematics Subject Classification ID

Other types of codes (94B60) Randomized algorithms (68W20)

Related Items (6)

Locality via Partially Lifted Codes ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Sparse affine-invariant linear codes are locally testable ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Invariance in Property Testing ⋮ On Sums of Locally Testable Affine Invariant Properties

Cites Work

• Unnamed Item
• Unnamed Item
• Self-testing/correcting with applications to numerical problems
• Efficient checking of polynomials and proofs and the hardness of approximation problems
• 2-transitivity is insufficient for local testability
• Nearly-linear size holographic proofs
• A combinatorial characterization of the testable graph properties
• Graph limits and parameter testing
• Testing low-degree polynomials over prime fields
• On Sums of Locally Testable Affine Invariant Properties
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Private information retrieval
• On the efficiency of local decoding procedures for error-correcting codes
• Locally testable codes and PCPs of almost-linear length
• Towards 3-query locally decodable codes of subexponential length
• Testing Reed–Muller Codes
• Simple PCPs with poly-log rate and query complexity
• Probabilistic checking of proofs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Optimal Testing of Reed-Muller Codes
• 3-query locally decodable codes of subexponential length
• Locally Testable Codes Require Redundant Testers
• Some results on cyclic codes which are invariant under the affine group and their applications
• Some 3CNF Properties Are Hard to Test
• Locally Decodable Codes
• The PCP theorem by gap amplification

This page was built for publication: Limits on the Rate of Locally Testable Affine-Invariant Codes