Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions

Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu +2

The Fourier-Entropy Influence (FEI) Conjecture states that for any Boolean function $f:\{+1,-1{\}}^n\to \{+1,-1\}$, the Fourier entropy of $f$ is at most its influence up to a unive…