Testing Reed–Muller Codes

DOI10.1109/TIT.2005.856958zbMath1247.94057OpenAlexW2146453677MaRDI QIDQ3546491

Tali Kaufman, Michael Krivelevich, Noga Alon, Dana Ron, Simon N. Litsyn

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.2005.856958

Mathematics Subject Classification ID

Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Randomized algorithms (68W20)

Related Items

Testing Odd-Cycle-Freeness in Boolean Functions ⋮ Quantum Locally Testable Codes ⋮ Making the Long Code Shorter ⋮ Local Testing of Lattices ⋮ Testing Linear-Invariant Properties ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An optimal tester for \(k\)-Linear ⋮ 2-transitivity is insufficient for local testability ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes ⋮ Unnamed Item ⋮ Local correction of juntas ⋮ An improved test of Boolean functions for \(k\)-dimensionality ⋮ Sample-Based High-Dimensional Convexity Testing. ⋮ Almost Optimal Testers for Concise Representations. ⋮ Symmetric LDPC codes and local testing ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ The Program of the Mini-Workshop ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Invariance in Property Testing ⋮ Testing Linear-Invariant Non-linear Properties: A Short Report ⋮ Optimal Testing of Reed-Muller Codes ⋮ Testing low-degree polynomials over prime fields ⋮ On Sums of Locally Testable Affine Invariant Properties ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ Unnamed Item ⋮ Almost optimal distribution-free junta testing ⋮ A unified framework for testing linear‐invariant properties ⋮ Testing computability by width-two OBDDs ⋮ Unnamed Item ⋮ Testing algebraic geometric codes ⋮ A combination of testability and decodability by tensor products ⋮ Unnamed Item ⋮ Reed-Muller Codes ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities ⋮ Direct Sum Testing

This page was built for publication: Testing Reed–Muller Codes