Abstract: 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
