Technical Report MSC-2014-05

Title: On The Structure of Boolean Functions with Small Spectral Norm
Authors: Ben Lee Volk
Supervisors: Amir Shpilka
Abstract: In this thesis we prove results regarding {0,1}oolean 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. $f$ can be computed by a De Morgan formula of size $O(2^{A^2} n^{2A+2})$ and by a De Morgan formula of depth $O( A^2 + \log(n) \cdot A)$.

4. 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$.

5. For every $\epsilon>0$ 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 (except 3) also hold (with a slight change in parameters) for functions $f:\Z_p^n\to \{0,1}$.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2014
To the main CS technical reports page

Computer science department, Technion