# Technical Report MSC-2014-05

 TR#: MSC-2014-05 Class: MSC Title: On The Structure of Boolean Functions with Small Spectral Norm Authors: Ben Lee Volk Supervisors: Amir Shpilka PDF MSC-2014-05.pdf 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}$. Copyright The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2014/MSC/MSC-2014-05), rather than to the URL of the PDF files directly. The latter URLs may change without notice.