A new upper bound on the query complexity of testing generalized Reed-Muller codes

DOI10.4086/TOC.2013.V009A025MaRDI QIDQ3191595zbMATH OpenOpenAlexFDO

Authors Noga Ron-Zewi, Madhu Sudan

Publication date 6 October 2014

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2013.v009a025

zbMATH Keywords

affine-invariant codeslocally testable codesquery complexityReed-Muller codes

Mathematics Subject Classification ID

Randomized algorithms (68W20) Linear codes (general theory) (94B05)

Recommendations

• A new upper bound on the query complexity for testing generalized Reed-Muller codes
• Optimal testing of Reed-Muller codes
• Testing Polynomials over General Fields
• Testing Reed–Muller Codes
• Optimal testing of multivariate polynomials over small prime fields

Cited in

(8)

• A new upper bound on the query complexity for testing generalized Reed-Muller codes
• Testing Polynomials over General Fields
• Testing Reed–Muller Codes
• Optimal testing of Reed-Muller codes
• Identifying generalized Reed-Muller codewords by quantum queries
• Property testing with online adversaries
• Improved optimal testing results from global hypercontractivity
• Property testing with online adversaries

This page was built for publication: A new upper bound on the query complexity of testing generalized Reed-Muller codes

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