The Fourier entropy-influence conjecture for certain classes of Boolean functions. (English)
Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4‒8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 330-341 (2011).
Summary: In 1996, Friedgut and Kalai made the Fourier entropy-influence conjecture: For every Boolean function $f : \{-1, 1\}^{n} \longrightarrow \{-1, 1\}$ it holds that $H[{\hat{f}}^{2}] \leq C \cdot I[f]$, where $H[{\hat{f}}^{2}]$ is the spectral entropy of $f$, $I[f]$ is the total influence of $f$, and $C$ is a universal constant. In this work we verify the conjecture for symmetric functions. More generally, we verify it for functions with symmetry group $S_{n_1} \times \cdots \times S_{n_d}$ where $d$ is constant. We also verify the conjecture for functions computable by read-once decision trees.