Boolean constant degree functions on the slice are junta

01/19/2018
by   Yuval Filmus, et al.
0

We show that a Boolean degree d function on the slice [n]k = { (x_1,...,x_n) ∈{0,1} : ∑_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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset