Optimal Testing of Reed-Muller Codes

DOI10.1007/978-3-642-16367-8_19zbMath1310.68227arXiv0910.0641OpenAlexW2949884761MaRDI QIDQ4933377

Swastik Kopparty, David Zuckerman, Madhu Sudan, Grant Schoenebeck, Arnab Bhattacharyya

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.0641

zbMATH Keywords

Gowers normlow-degree polynomialsaffine-invariant codes

Mathematics Subject Classification ID

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

Related Items

Making the Long Code Shorter ⋮ Local Testing of Lattices ⋮ A new lower bound on the second-order nonlinearity of a class of monomial bent functions ⋮ PCPs via the low-degree long code and hardness for constrained hypergraph coloring ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An optimal tester for \(k\)-Linear ⋮ On Active and Passive Testing ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ Unnamed Item ⋮ An improved test of Boolean functions for \(k\)-dimensionality ⋮ Sample-Based High-Dimensional Convexity Testing. ⋮ Almost Optimal Testers for Concise Representations. ⋮ Optimal Testing of Reed-Muller Codes ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ Improving lower bounds on the second-order nonlinearity of three classes of Boolean functions ⋮ Almost optimal distribution-free junta testing ⋮ Testing properties of functions on finite groups ⋮ Unnamed Item ⋮ Direct Sum Testing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• A new proof of Szemerédi's theorem for arithmetic progressions of length four
• Self-testing/correcting with applications to numerical problems
• Linearity testing in characteristic two
• Property testing and its connection to learning and approximation
• Testing Reed–Muller Codes
• The distribution of polynomials over finite fields, with applications to the Gowers norms
• Interactive proofs and the hardness of approximating cliques
• Robust Characterizations of Polynomials with Applications to Program Testing
• Optimal Testing of Reed-Muller Codes
• Hierarchy Theorems for Property Testing
• A new proof of Szemerédi's theorem