Event calendar file
School of Technology and Computer Science Seminars
On the Structure of Boolean Functions With Small Spectral Norm
by Mr. Swagato Sanyal (School of Technology and Computer Science, TIFR)
Friday, July 18, 2014
from
to
(Asia/Kolkata)
at Colaba Campus ( D-405 (D-Block Seminar Room) )
at Colaba Campus ( D-405 (D-Block Seminar Room) )
| Description |
Let f: F_2^n -> {+1, -1} be a Boolean function with the first Fourier norm A and Fourier sparsity s. We will prove that there is an affine subspace of the vector space F_2^n, of dimension O(A), on which the f is constant. If time permits, we will prove that f has a parity decision tree of depth O(\sqrt{s}). These results are by Tsang et al which improves on earlier results by Shpilka et al.
References:
Amir Shpilka, Avishay Tal, Ben lee Volk. On the Structure of Boolean Functions with Small Spectral Norm. ITCS 2014
Hing Yin Tsang, Chung Hoi Wong, Ning Xie, Shengyu Zhang. Fourier sparsity, spectral norm and the log rank conjecture. FOCS 2013
|
