Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture

Andrew Wan, John Wright, Chenggang Wu

Given $f:\{-1,1{\}}^n\to \{-1,1\}$, define the \emph{spectral distribution} of $f$ to be the distribution on subsets of $[n]$ in which the set $S$ is sampled with probabil…