M.Sc Thesis
M.Sc Student Volk Ben Lee On the Structure of Boolean Functions with Small Spectral Norm Department of Computer Science Professor Amir Shpilka

Abstract

In this thesis we prove 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 functions f : {0,1}n → {0,1} with spectral norm A.

1. There is a subspace V of co-dimension at most A2 such that f|V is constant.

2. f can be computed by a parity decision tree of size 2A2 n2A. (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(2A2 n2A2) and by a De Morgan formula of depth O(A2 log(n) ∙ 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 A2 log s.

5. For every ε>0 there is a parity decision tree of depth O(A2 log(1/ ε)) and size 2O(A2) min { 1/ ε2, O(log(1/ ε))2A} that ε-approximates f. Furthermore, this tree can be learned, with  probability 1-δ, using poly(n, exp(A2),1/ ε, log(1/ δ)) membership queries.

All the results above (except 3) also hold (with a slight change in parameters) for functions f:Zpn → {0,1}.