[CSDM] Ben lee Volk at theory lunch, Friday Sep 20,

[Zeev Dvir]

Hi all,

This Friday we will have a talk by Ben lee Volk. See title and abstract
below.

Lunch will be served at 11:45 and the talk will start noon. Room is COS 402.

-zeev

------------------------
Title: On the Structure of Boolean Functions with Small Spectral Norm

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/eps)). Furthermore, this tree can be efficiently learned
using membership queries.

All the results above also hold (with a slight change in parameters) to
functions over (Z_p)^n.

Based on joint work with Amir Shpilka and Avishay Tal
-------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20130918/d888b4ec/attachment.html>