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 TR16-007 | 23rd January 2016 20:43

Property Testing, PCP, andJuntas

RSS-Feed




Revision #1
Authors: Guy Kindler
Accepted on: 23rd January 2016 20:43
Downloads: 371
Keywords: 


Abstract:

This is a PhD Thesis, originally published in 2003, and put here now for accessibility, not novelty.

The first part of this thesis strengthens the low-error PCP
characterization of NP, coming closer to the upper limit of the
conjecture of BGLR. This result has been surpassed -- see the paper
"Polynomially Low Error PCPs with polyloglog n Queries via Modular
Composition" with Irit Dinur and Prahladh Harsha.

In the second part we show that a boolean function over
$n$ variables can be tested for the property of depending on only
$k$ of them, using a number of queries that depends only on $k$
and the approximation parameter $\epsilon$. After the thesis was
published, almost optimal parameters were obtained in the paper
"Testing Juntas Nearly Optimally" by E. Blais.

In the third part of this thesis we show that any boolean function
$f\colon\{0,1\}^n\to\{-1,1\}$ whose weight on Fourier-Walsh
products of size larger than $k$ is bounded by
$(\epsilon/k)^{(\ell+1)/\ell}$, where $\ell$ is any fixed positive
integer, is $O(\epsilon)$-close to a junta whose size is independent of
$n$. We also show that for small values of $\epsilon$, if the
weight of a boolean function $f$ on Fourier-Walsh products of size
larger than $k$ is $\epsilon$, then $f$ is $\epsilon(1+o(1))$-close to
a junta, whose size depends only on $k$. This is a generalization of
the result in~\cite{FKN}, who proved this for $k=1$, and only with
respect to the uniform measure. The first part of this result was
surpassed even before it was published by a paper named "On the
distribution of the Fourier spectrum of Boolean functions" by J.
Bourgain. A much simpler proof with improved parameters can be
found in a paper named "Gaussian noise sensitivity and Fourier tails"
with Ryan O`Donnell.


Paper:

TR16-007 | 23rd January 2016 06:43

Property Testing, PCP, andJuntas





TR16-007
Authors: Guy Kindler
Publication: 23rd January 2016 14:08
Downloads: 358
Keywords: 


Abstract:

The first part of this thesis strengthens the low-error PCP
characterization of NP, coming closer to the upper limit of the
conjecture of~\cite{BGLR}.

In the second part we show that a boolean function over
$n$ variables can be tested for the property of depending on only
$\size$ of them, using a number of queries that depends only on $\size$
and the approximation parameter $\err$.

In the third part of this thesis we show that any boolean function
$\f\colon\{0,1\}^n\to\{-1,1\}$ whose weight on Fourier-Walsh
products of size larger than $k$ is bounded by
$(\epsilon/k)^{(\ell+1)/\ell}$, where $\ell$ is any fixed positive
integer, is $O(\epsilon)$-close to a junta whose size is independent of
$n$. We also show that for small values of $\epsilon$, if the
weight of a boolean function $\f$ on Fourier-Walsh products of size
larger than $k$ is $\epsilon$, then $\f$ is $\epsilon(1+o(1))$-close to
a junta, whose size depends only on $k$. This is a generalization of
the result in~\cite{FKN}, who proved this for $k=1$, and only with
respect to the uniform measure.



ISSN 1433-8092 | Imprint