דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

On The Structure of Boolean Functions with Small Spectral Norm
event speaker icon
בן לי וולק, הרצאה סמינריונית למגיסטר
event date icon
יום רביעי, 27.11.2013, 12:30
event location icon
טאוב 201
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.
[בחזרה לאינדקס האירועים]