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.

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.