Boolean Functions with Minimal Spectral Sensitivity

Krišjānis Prūsis, Jevgēnijs Vihrovs

We show examples of total Boolean functions that depend on $n$ variables and have spectral sensitivity $\Theta (\sqrt{\log n})$, which is asymptotically minimal. Our main new function co…