Lower bounds for adaptive linearity tests

Author Shachar Lovett



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1313.pdf
  • Filesize: 166 kB
  • 12 pages

Document Identifiers

Author Details

Shachar Lovett

Cite As Get BibTex

Shachar Lovett. Lower bounds for adaptive linearity tests. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 515-526, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008) https://doi.org/10.4230/LIPIcs.STACS.2008.1313

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.

Subject Classification

Keywords
  • Property testing
  • Linearity testing
  • Adaptive tests
  • Lower Property testing
  • Linearity testing
  • Adaptive tests
  • Lower

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail