On the Structure of Boolean Functions with Small Spectral Norm

Abstract

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is $\Vert \hat{f}{\Vert }_1={\sum }_{\alpha }|\hat{f}(\alpha )|$). Specifically, we prove the following results for functions $f:\{0,1{\}}^n\to \{0,1\}$ with $\Vert \hat{f}{\Vert }_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 ε-approximates f. Furthermore, this tree can be learned, with probability $1-\delta$, using $\poly(n,\exp(A^2),1/ε,\log(1/δ))$ membership queries. All the results above also hold (with a slight change in parameters) to functions $f:Z_p^n\to \{0,1\}$.

Cited by in corpus (1)

• Fourier sparsity, spectral norm, and the Log-rank conjecture