Gopalan-Servedio Conjecture

The Gopalan-Servedio conjecture asserts that a nonconstant Boolean function $f:{-1,1}^n->{-1,1}$ of polynomial degree satisfies

$sum_(i=1)^n|f^^({i})|<=sqrt(d),$

where $f^^({i})=E[f(X)X_i]$ is a coefficient of its Boolean Fourier expansion under the uniform distribution (O'Donnell 2021). Here is the total degree of the representing real multilinear polynomial. Reversing selected input coordinates can make all these coefficients nonnegative without changing , so the version with a signed sum is equivalent.