<div dir="ltr">Hi all,<div><br></div><div>This Friday we will have a talk by Ben lee Volk. See title and abstract below.</div><div><br></div><div>Lunch will be served at 11:45 and the talk will start noon. Room is COS 402.</div>

<div><br></div><div>-zeev</div><div><br></div><div>------------------------</div><div><div>Title: On the Structure of Boolean Functions with Small Spectral Norm</div><div><br></div><div>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. </div>

<div><br></div><div>1. There is a subspace V of co-dimension at most A^2 such that f|_V is constant.</div><div><br></div><div>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.)</div>

<div><br></div><div>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.</div><div><br></div><div>4. For a &quot;small&quot; A, f can be epsilon-approximated by a parity decision tree of depth O(log(1/eps)). Furthermore, this tree can be efficiently learned using membership queries.</div>

<div><br></div><div>All the results above also hold (with a slight change in parameters) to functions over (Z_p)^n. </div><div><br></div><div>Based on joint work with Amir Shpilka and Avishay Tal</div></div><div>-------------</div>

</div>