A tighter bound on the number of relevant variables in a bounded degree Boolean function

Abstract

A classical theorem of Nisan and Szegedy says that a boolean function with degree $d$ as a real polynomial depends on at most $d{2}^{d-1}$ of its variables. In recent work by Chiarelli, Hatami and Saks, this upper bound was improved to $C\cdot 2^d$, where $C=6.614$. Here we refine their argument to show that one may take $C=4.416$.

8 pages