Testing Reed–Muller Codes

DOI10.1109/TIT.2005.856958MaRDI QIDQ3546491zbMATH OpenOpenAlexFDO

Authors Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron, Simon 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

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

Recommendations

• Optimal testing of Reed-Muller codes
• Testing algebraic geometric codes
• A new upper bound on the query complexity of testing generalized Reed-Muller codes
• A new upper bound on the query complexity for testing generalized Reed-Muller codes
• Testing Polynomials over General Fields

Cited in

(51)

• Testing Odd-Cycle-Freeness in Boolean Functions
• Data stream algorithms for codeword testing (extended abstract)
• On Sums of Locally Testable Affine Invariant Properties
• Testing Linear-Invariant Properties
• A unified framework for testing linear-invariant properties
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• Making the Long Code Shorter
• Almost optimal distribution-free junta testing
• Local decoding and testing of polynomials over grids
• Improved optimal testing results from global hypercontractivity
• Towards lower bounds on locally testable codes via density arguments
• Local testing of lattices
• The program of the mini-workshop
• Testing Linear-Invariant Non-linear Properties: A Short Report
• Local correction of juntas
• A combination of testability and decodability by tensor products
• Using Reed-Muller codes in self-testing circuits
• Agreement tests on graphs and hypergraphs
• A new upper bound on the query complexity for testing generalized Reed-Muller codes
• Direct sum testing
• Testing odd-cycle-freeness in Boolean functions
• Property testing with online adversaries
• Exponentially improved algorithms and lower bounds for testing signed majorities
• A new upper bound on the query complexity of testing generalized Reed-Muller codes
• An improved test of Boolean functions for \(k\)-dimensionality
• Bounds on \(2\)-query codeword testing
• Coxeter codes: extending the Reed-Muller family
• Reed-Muller Codes
• On axis-parallel tests for tensor product codes
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Invariance in property testing
• One-sided error testing of monomials and affine subspaces
• On counting t-cliques mod 2
• Testing algebraic geometric codes
• Robust multiplication-based tests for Reed-Muller codes
• Local testing for membership in lattices
• Quantum locally testable codes
• Testing low-degree polynomials over prime fields
• Sample-based high-dimensional convexity testing
• On axis-parallel tests for tensor product codes
• Property testing with online adversaries
• An optimal tester for k-Linear
• Optimal testing of Reed-Muller codes
• Testing computability by width-two OBDDs
• Explicit strong LTCs with inverse poly-log rate and constant soundness
• 2-transitivity is insufficient for local testability
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
• Almost Optimal Testers for Concise Representations.
• Symmetric LDPC codes and local testing
• Stabilizer testing and magic entropy via quantum Fourier analysis
• Limitation on the Rate of Families of Locally Testable Codes

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

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