License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1313
URN: urn:nbn:de:0030-drops-13132
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1313/
Go to the corresponding LIPIcs Volume Portal

Lovett, Shachar

Lower bounds for adaptive linearity tests

pdf-format:
22011.LovettShachar.Paper.1313.pdf (0.2 MB)

Abstract

Linearity tests are randomized algorithms which have oracle access
to the truth table of some function f, and are supposed to
distinguish between linear functions and functions which are far
from linear. Linearity tests were first introduced by (Blum, Luby
and Rubenfeld, 1993), 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.

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
(Samorodnitsky and Trevisan 2000) constructed the Complete Graph
Test, and prove that no Hyper Graph Test can perform better than
the Complete Graph Test. Later in (Samorodnitsky and Trevisan
2006) 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 the Gowers Norm. A
result by (Ben-Sasson, Harsha and Raskhodnikova 2005) 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 (Samorodnitsky and Trevisan 2006). We also
study, like (Samorodnitsky and Trevisan 2006), 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.

BibTeX - Entry

@InProceedings{lovett:LIPIcs:2008:1313,
  author =	{Shachar Lovett},
  title =	{{Lower bounds for adaptive linearity tests}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{515--526},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1313},
  URN =		{urn:nbn:de:0030-drops-13132},
  doi =		{10.4230/LIPIcs.STACS.2008.1313},
  annote =	{Keywords: Property testing, Linearity testing, Adaptive tests, Lower Property testing, Linearity testing, Adaptive tests, Lower}
}

Keywords: Property testing, Linearity testing, Adaptive tests, Lower Property testing, Linearity testing, Adaptive tests, Lower
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI