M.Sc Thesis


M.Sc StudentVolk Ben Lee
SubjectOn the Structure of Boolean Functions with Small Spectral
Norm
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Amir Shpilka
Full Thesis textFull thesis text - English Version


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}.