On The Structure of Boolean Functions with Small Spectral Norm

Ben Lee Volk, M.Sc. Thesis Seminar

Wednesday, 27.11.2013, 12:30

Taub 201

In this talk we show several results regarding Boolean functions with small spectral norm (the spectral norm of $f$ is the sum of the absolute value of its Fourier coefficients.) Specifically, we prove the following results for Boolean functions on n variables with spectral norm $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 a "small" $A$, $f$ can be epsilon-approximated by a parity decision tree of depth $O(\log(1/\epsilon))$. Furthermore, this tree can be efficiently learned using membership queries. Furthermore, this tree can be efficiently learned using membership queries.
All the results above also hold (with a slight change in parameters) for functions $f:\mathbb{Z}_p^n\to \{0,1\}$.
Based on joint work with Amir Shpilka and Avishay Tal.