Boolean functions violate the square-root degree bound by arbitrary factors

Formal proof listed 1 paper September 26, 2026
What the paper claims, in its own words

Disproves the proposed square-root bound relating a Boolean function's linear Fourier coefficients to its polynomial degree. For every C > 0, there is a sign-valued Boolean function f with ∑if^({i})>Cdeg⁡(f)\sum_i\widehat f(\{i\})\gt C\sqrt{\deg(f)}. Thus its total signed correlation with individual input bits can exceed the proposed bound by an arbitrary factor.

The plain-language explainer for this entry is still coming.

The original paper