Optimal testing of Reed-Muller codes

DOI10.1007/978-3-642-16367-8_19MaRDI QIDQ4933377zbMATH OpenOpenAlexFDO

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

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

affine-invariant codesGowers normlow-degree polynomials

Mathematics Subject Classification ID

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

Abstract: We consider the problem of testing if a given function f : F_2^n -> F_2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. The Gowers norm is based on a natural 2^{d+1}-query test for this property. Alon et al. [AKKLR05] rediscovered this test and showed that it accepts every degree d polynomial with probability 1, while it rejects functions that are Omega(1)-far with probability Omega(1/(d 2^{d})). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Omega(2^{-d})-far with Omega(1)-probability (so the rejection probability is a universal constant independent of d and n). This implies a tight relationship between the (d+1)st Gowers norm of a function and its maximal correlation with degree d polynomials, when the correlation is close to 1. Our proof works by induction on n and yields a new analysis of even the classical Blum-Luby-Rubinfeld [BLR93] linearity test, for the setting of functions mapping F_2^n to F_2. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [GT09,LMS08]. Our result has several implications. First, it shows that the Gowers norm test is tolerant, in that it also accepts close codewords. Second, it improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson [VW07]. Third, it implies a "query hierarchy" result for property testing of affine-invariant properties. That is, for every function q(n), it gives an affine-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of [GKNR09] for graph properties.

Recommendations

• 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 Reed–Muller Codes
• Testing low complexity affine-invariant properties
• Optimal testing of multivariate polynomials over small prime fields

Cites work

• A new proof of Szemerédi's theorem
• A new proof of Szemerédi's theorem for arithmetic progressions of length four
• Algebraic property testing: the role of invariance
• Hierarchy theorems for property testing
• scientific article; zbMATH DE number 4130567 (Why is no real title available?)
• Interactive proofs and the hardness of approximating cliques
• Inverse conjecture for the Gowers norm is false
• Linearity testing in characteristic two
• Non-deterministic exponential time has two-prover interactive protocols
• Optimal testing of Reed-Muller codes
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Testing Reed–Muller Codes
• The distribution of polynomials over finite fields, with applications to the Gowers norms
• Trivial Selmer groups and even partitions of a graph

Cited in

(32)

• Algebraic testing and weight distributions of codes.
• 2-transitivity is insufficient for local testability
• A new lower bound on the second-order nonlinearity of a class of monomial bent functions
• Improving lower bounds on the second-order nonlinearity of three classes of Boolean functions
• An optimal tester for k-Linear
• Testing properties of functions on finite groups
• Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
• Testing low-degree polynomials over prime fields
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• A new upper bound on the query complexity for testing generalized Reed-Muller codes
• A new upper bound on the query complexity of testing generalized Reed-Muller codes
• Testing Polynomials over General Fields
• Making the Long Code Shorter
• Testing Reed–Muller Codes
• Low-degree tests at large distances
• A query efficient non-adaptive long code test with perfect completeness
• Local testing of lattices
• Robust multiplication-based tests for Reed-Muller codes
• An improved test of Boolean functions for \(k\)-dimensionality
• Optimal testing of Reed-Muller codes
• Identifying generalized Reed-Muller codewords by quantum queries
• Local decoding and testing of polynomials over grids
• Sample-based high-dimensional convexity testing
• On axis-parallel tests for tensor product codes
• Explicit strong LTCs with inverse poly-log rate and constant soundness
• Almost optimal distribution-free junta testing
• On axis-parallel tests for tensor product codes
• Direct sum testing
• On active and passive testing
• Almost Optimal Testers for Concise Representations.
• The Gowers U₃ norm of one family of cubic power permutations
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring

This page was built for publication: Optimal testing of Reed-Muller codes

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