טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentVolk Ben Lee
SubjectOn the Structure of Boolean Functions with Small Spectral
Norm
DepartmentDepartment of Computer Science
Supervisor Professor 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}.