Testing Reed–Muller Codes

DOI10.1109/TIT.2005.856958zbMath1247.94057MaRDI 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

94B27: Geometric methods (including applications of algebraic geometry) applied to coding theory

68W20: Randomized algorithms

Related Items

Local Testing of Lattices, Unnamed Item, Unnamed Item, Unnamed Item, 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, Unnamed Item, A unified framework for testing linear‐invariant properties, Unnamed Item, Testing Linear-Invariant Properties, Sample-Based High-Dimensional Convexity Testing., Almost optimal distribution-free junta testing, A combination of testability and decodability by tensor products, Direct Sum Testing, Unnamed Item, Reed-Muller Codes, Almost Optimal Testers for Concise Representations., Local correction of juntas, An improved test of Boolean functions for \(k\)-dimensionality, Symmetric LDPC codes and local testing, Towards lower bounds on locally testable codes via density arguments, Testing computability by width-two OBDDs, Testing algebraic geometric codes, 2-transitivity is insufficient for local testability, Exponentially improved algorithms and lower bounds for testing signed majorities, An optimal tester for \(k\)-Linear, Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial 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, Testing Odd-Cycle-Freeness in Boolean Functions, Quantum Locally Testable Codes, Making the Long Code Shorter