M.Sc Student | Volk Ben Lee |
---|---|

Subject | On the Structure of Boolean Functions with Small Spectral Norm |

Department | Department of Computer Science |

Supervisor | Professor Amir Shpilka |

Full Thesis text |

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 *A ^{2}* such that

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. *f* can be computed by a De
Morgan formula of size *O*(2^{A}^{2}* n*^{2A2})
and by a De Morgan formula of depth *O*(*A ^{2} *log(

4. 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*.

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

All the results above (except 3) also
hold (with a slight change in parameters) for functions *f*:*Z*_{p}^{n}
→ {0,1}.