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.