Boolean constant degree functions on the slice are juntas

Abstract

We show that a Boolean degree $d$ function on the slice $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)=\{(x_1,\dots ,x_n)\in \{0,1\}:{\sum }_{i=1}^n{x}_i=k\}$ is a junta, assuming that $k,n-k$ are large enough. This generalizes a classical result of Nisan and Szegedy on the hypercube. Moreover, we show that the maximum number of coordinates that a Boolean degree $d$ function can depend on is the same on the slice and the hypercube.

arXiv comment10 pages