Tight Bound on the Number of Relevant Variables in a Bounded degree Boolean function
share
In this paper, we prove that a degree d Boolean function depends on at most C· 2^d variables for some C<22, i.e. it is a C· 2^d-junta. This improves the d· 2^d-1 upper bound of Nisan and Szegedy [NS94]. Our proof uses a new weighting scheme where we assign weights to variables based on the highest degree monomial they appear on. We note that a bound of C· 2^d is essentially tight. A lower bound of 2^d-1 can easily be achieved by a read-once decision tree of depth d (see [O'Donnell 14], Exercise 3.24). We slightly improve this bound by constructing a Boolean function of degree d with 3· 2^d-1-2 relevant variables. This construction was independently observed by Avishay Tal, but has not appeared in a publication before [Tal 17].
READ FULL TEXT