In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function.
Specifically, we prove that for every non-linear and symmetric f:\{0,1\}^{k} \to \{0,1\} there exists a set \emptyset\neq S\subset[k] such that |S|=O(\Gamma(k)+\sqrt{k}), and \hat{f}(S) \neq 0, where ... more >>>