Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR07-090 | 8th October 2007 00:00

Lower bounds for Adaptive Linearity Tests without using the Gowers Norm

RSS-Feed




Revision #1
Authors: Shachar Lovett
Accepted on: 8th October 2007 00:00
Downloads: 1073
Keywords: 


Abstract:

Linearity tests are randomized algorithms which have oracle access to the truth table of some function f, which are supposed to distinguish between linear functions and functions which are far from linear. Linearity tests were first introduced by Blum,Luby and Rubenfeld in [BLR93], and were later used in the PCP theorem among other applications. The quality of a linearity test is described by its correctness c - the probability it accepts linear functions, its soundness s - the probability it accepts functions far from linear, and its query complexity q - the number of queries it makes.
The BLR test had $q=3$ and $s=1/2$. Linearity tests were studied in order to decrease the soundness of linearity tests, while keeping the query complexity small (for one reason, to improve PCP constructions). Samorodnitsky and Trevisan constructed in [ST00] the Complete Graph Test, which for every $k \in \N$ has $q ={k \choose 2} + k$ and $s=2^{-{k \choose 2}}$. They prove that no Hyper Graph Test can perform better than the Complete Graph Test. Later in [ST06] they prove, among other results, that no non-adaptive linearity test can perform better than the Complete Graph Test. Their proof uses the algebraic machinery of Gowers Norm. A result by Ben-Sasson, Harsha and Raskhodnikova [BHR05]
allows to generalize this lower bound also to adaptive linearity tests.
We also prove the same optimal lower bound for adaptive linearity test, but our proof technique is arguably simpler and more direct than the one used in [ST06]. We also study, like [ST06], the behavior of linearity tests on quadratic functions. However, instead of analyzing the Gowers Norm of certain functions, we provide a more direct combinatorial proof, studying the behavior of linearity tests on random quadratic functions. This proof technique also lets us prove directly the lower bound also for adaptive linearity tests.


Paper:

TR07-090 | 11th September 2007 00:00

Tight lower bounds for adaptive linearity tests





TR07-090
Authors: Shachar Lovett
Publication: 24th September 2007 13:46
Downloads: 1264
Keywords: 


Abstract:

Linearity tests are randomized algorithms which have oracle access to the truth table of some function $f$,
which are supposed to distinguish between linear functions and functions which are far from linear. Linearity tests were first introduced by Blum, Luby and Rubenfeld in \cite{BLR93}, and were later used in the PCP theorem among other applications. The quality of a linearity test is described by its \emph{correctness} $c$ - the probability it accepts linear functions, its {soundness} $s$ - the probability it accepts functions far from linear, and its \emph {query complexity} $q$ - the number of queries it makes. The BLR test had $q=3$ and $s=1/2$. Linearity tests were studied in order to decrease the soundness of linearity tests, while keeping the query complexity small (for one reason, to improve PCP constructions). Samorodnitsky and Trevisan constructed in \cite{ST00} the Complete Graph Test, which for every $k \in \N$ has $q={k \choose 2}+k$ and $s=2^{-{k \choose 2}}$. They prove that no Hyper Graph Test can perform better than the Complete Graph Test. Later in \cite{ST06} they prove, among other results, that no non-adaptive linearity test can perform better than the Complete Graph Test. We generalize their result for adaptive tests, and prove that the Complete Graph Test is optimal even against adaptive linearity tests. Our lower bound is actually proven in a more general setting, considering the \emph{Average Query Complexity} of a linearity test. Our proof technique is somewhat different from the one used in \cite{ST06}. In both cases the behavior of linearity tests against quadratic functions are considered, but while \cite{ST06} uses algebraic analysis of the Gowers Norm of certain functions, we use a more direct combinatorial approach, which allows us to also handle the case of adaptive linearity tests.


Comment(s):

Comment #1 to TR07-090 | 8th February 2008 07:01

The result proven was already known Comment on: TR07-090





Comment #1
Authors: Shachar Lovett
Accepted on: 8th February 2008 07:01
Downloads: 1291
Keywords: 


Abstract:

The result of the paper can be deduced from already known
results in [ST06] and
[BHR05].




ISSN 1433-8092 | Imprint