On the Structure of Boolean Functions with Small Spectral Norm

الأصل · EN

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is f₁=∑α|f(α)|). Specifically, we prove the following results for functions f:{0,1}ⁿ → {0,1} with f₁=A. 1. There is a subspace V of co-dimension at most A² such that f|ᵥ is constant. 2. f can be computed by a parity decision tree of size 2ᵃ²n²ᵃ. (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² s. 4. For every 0<ε there is a parity decision tree of depth O(A² + (1/ε)) and size 2ᵒ⁽ᵃ²⁾ · {1/ε²,O((1/ε))²ᵃ} that ε-approximates f. Furthermore, this tree can be learned, with probability 1-δ, using (n,(A²),1/ε,(1/δ)) membership queries. All the results above also hold (with a slight change in parameters) to functions f:Zₚⁿ→ {0,1}.