Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

On The Structure of Boolean Functions with Small Spectral Norm
event speaker icon
Ben Lee Volk (M.Sc. Thesis Seminar)
event date icon
Wednesday, 27.11.2013, 12:30
event location icon
Taub 201
event speaker icon
Advisor: Prof. Amir Shpilka
In this talk we show several 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 Boolean functions on n variables with spectral norm $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. 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$. 4. For a "small" $A$, $f$ can be epsilon-approximated by a parity decision tree of depth $O(\log(1/\epsilon))$. Furthermore, this tree can be efficiently learned using membership queries. Furthermore, this tree can be efficiently learned using membership queries. All the results above also hold (with a slight change in parameters) for functions $f:\mathbb{Z}_p^n\to \{0,1\}$. Based on joint work with Amir Shpilka and Avishay Tal.