TR#: | MSC-2014-05 |

Class: | MSC |

Title: | On The Structure of Boolean Functions with Small Spectral Norm |

Authors: | Ben Lee Volk |

Supervisors: | Amir Shpilka |

MSC-2014-05.pdf | |

Abstract: | In this thesis we prove results regarding {0,1}oolean functions with small spectral norm (the spectral norm of $f$ is $\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions $f:\{0,1}^n\to \{0,1}$ with $\|\hat{f}\|_1=A$.
1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant. 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^{2A+2})$ and by a De Morgan formula of depth $O( A^2 + \log(n) \cdot 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 $A^2\log s$. 5. For every $\epsilon>0$ there is a parity decision tree of depth $O(A^2 + \log(1/\epsilon))$ and size $2^{O(A^2)} \cdot \min\{ 1/\epsilon^2,O(\log(1/\epsilon))^{2A}\}$ that $\epsilon$-approximates $f$. Furthermore, this tree can be learned, with probability $1-\delta$, using $\poly(n,\exp(A^2),1/\epsilon,\log(1/\delta))$ membership queries. All the results above (except 3) also hold (with a slight change in parameters) for functions $f:\Z_p^n\to \{0,1}$. |

Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2014/MSC/MSC-2014-05), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2014

To the main CS technical reports page