Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SYMMETRIC FUNCTION, FOURIER SPECTRUM, LEARNING JUNTAS:
Reports tagged with Symmetric function, Fourier Spectrum, Learning Juntas:
TR10-178 | 17th November 2010
Amir Shpilka, Avishay Tal

#### On the Minimal Fourier Degree of Symmetric Boolean Functions

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

ISSN 1433-8092 | Imprint