1 Search Results for "Litsyn, Simon"


Document
Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)

Authors: Tali Kaufman, Simon Litsyn, and Ning Xie

Published in: Dagstuhl Seminar Proceedings, Volume 8341, Sublinear Algorithms (2008)


Abstract
For Boolean functions that are $epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $extsc{rej}(epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for $extsc{rej}(epsilon)$ were obtained by Bellare, Coppersmith, H{{a}}stad, Kiwi and Sudan. They used Fourier analysis to show that $ extsc{rej}(epsilon) geq e$ for every $0 leq epsilon leq frac{1}{2}$. They also conjectured that this bound might not be tight for $epsilon$'s which are close to $1/2$. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of $ extsc{rej}(epsilon) geq epsilon$ by an additive constant that depends only on $epsilon$: $extsc{rej}(epsilon) geq epsilon + min {1376epsilon^{3}(1-2epsilon)^{12}, frac{1}{4}epsilon(1-2epsilon)^{4}}$, for every $0 leq epsilon leq frac{1}{2}$. Our analysis is based on a relationship between $extsc{rej}(epsilon)$ and the weight distribution of a coset of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution.

Cite as

Tali Kaufman, Simon Litsyn, and Ning Xie. Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2). In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:DagSemProc.08341.3,
  author =	{Kaufman, Tali and Litsyn, Simon and Xie, Ning},
  title =	{{Breaking the \$\backslashepsilon\$-Soundness Bound of the Linearity Test over GF(2)}},
  booktitle =	{Sublinear Algorithms},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8341},
  editor =	{Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.3},
  URN =		{urn:nbn:de:0030-drops-16971},
  doi =		{10.4230/DagSemProc.08341.3},
  annote =	{Keywords: Linearity test, Fourier analysis, coding theory}
}
  • Refine by Author
  • 1 Kaufman, Tali
  • 1 Litsyn, Simon
  • 1 Xie, Ning

  • Refine by Classification

  • Refine by Keyword
  • 1 Fourier analysis
  • 1 Linearity test
  • 1 coding theory

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2008

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