Revision #1 Authors: Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

Accepted on: 9th April 2010 03:09

Downloads: 997

Keywords:

We consider the problem of testing if a given function $f : \mathbb{F}_2^n \rightarrow \mathbb{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)^{\rm{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 $\mathbb{F}_2^n$ to $\mathbb{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.

TR09-086 Authors: Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

Publication: 2nd October 2009 05:00

Downloads: 1280

Keywords:

We consider the problem of testing if a given function

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

every degree $d$ polynomial with probability $1$, while rejecting

functions that are $\Omega(1)$-far with probability

$\Omega(1/(d 2^{d}))$.

We give an asymptotically optimal analysis of their test showing

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$).

Our proof works by induction on $n$, and yields a new analysis of

even the

classical Blum-Luby-Rubinfeld~\cite{BLR} 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 \cite{GT,LMS}.

Our result gives a new relationship between

the $(d+1)^{\rm{st}}$-Gowers norm of a function and its maximal

correlation with degree $d$ polynomials. For functions highly correlated

with degree $d$ polynomials, this relationship is asymptotically

optimal.

Our improved analysis of the \cite{AKKLR}-test also improves the

parameters of an XOR lemma for polynomials given by Viola and

Wigderson~\cite{VW}.

Finally, the optimality of our result also implies a ``query-hierarchy''

result for property testing of linear-invariant properties: For every

function $q(n)$, it gives a linear-invariant property that is testable

with $O(q(n))$-queries, but not with $o(q(n))$-queries, complementing

an analogous result of \cite{GKNR08} for graph properties.