The Taub Faculty of Computer Science Events and Talks

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.