  In this paper we prove results regarding Boolean functions with small
spectral norm (the spectral norm of f is
$\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the
following results for functions $f:\{0,1\}^n \to \{0,1\}$ with
$\|\hat{f}\|_1=A$.
  1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is
constant.
  2. f can be computed by a parity decision tree of size $2^{A^2}n^{2A}$. (a
parity decision tree is a decision tree whose nodes are labeled with arbitrary
linear functions.)
  3. If in addition f has at most s nonzero Fourier coefficients, then f can be
computed by a parity decision tree of depth $A^2 \log s$.
  4. For every $0<\epsilon$ there is a parity decision tree of depth $O(A^2 +
\log(1/\epsilon))$ and size $2^{O(A^2)} \cdot
\min\{1/\epsilon^2,O(\log(1/\epsilon))^{2A}\}$ that \epsilon-approximates f.
Furthermore, this tree can be learned, with probability $1-\delta$, using
$\poly(n,\exp(A^2),1/\epsilon,\log(1/\delta))$ membership queries.
  All the results above also hold (with a slight change in parameters) to
functions $f:Z_p^n\to \{0,1\}$.
