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

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
בן לי וולק (הרצאה סמינריונית למגיסטר)
event date icon
יום רביעי, 27.11.2013, 12:30
event location icon
Taub 201
event speaker icon
מנחה: 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.