On the Structure of Boolean Functions With Small Spectral Norm

by Mr Swagato Sanyal (School of Technology and Computer Science, TIFR)

Friday 18 Jul 2014, 14:30 → 16:00 Asia/Kolkata

D-405 (D-Block Seminar Room) (Colaba Campus)

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