Optimal testing of reed-muller codes

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

64 Scopus citations

Abstract

We consider the problem of testing if a given function f : double-struck F2n → double-struck F2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al. [1] proposed and analyzed a natural 2d+1-query test for this problem. This test turned out to be intimately related to the Gowers norm. Alon et. al. showed that this test accepts every degree d polynomial with probability 1, while it rejects functions that are Ω(1)-far with probability Ω(1/(d2d)). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Ω(2-d)-far with Ω(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 [2] linearity test, for the setting of functions mapping double-struck F2n to double-struck F2. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [3], [4]. 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 [5]. 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 [6] for graph properties.

Original languageEnglish (US)
Title of host publicationProceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Pages488-497
Number of pages10
DOIs
StatePublished - 2010
Externally publishedYes
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, NV, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
CountryUnited States
CityLas Vegas, NV
Period10/23/1010/26/10

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Gowers norm
  • Low-degree tests
  • Property testing
  • Reed-Muller codes
  • Sublinear-time algorithms

Fingerprint Dive into the research topics of 'Optimal testing of reed-muller codes'. Together they form a unique fingerprint.

Cite this