We study the deterministic query complexity of Boolean functions on slices of the hypercube. The $k^{ th}$ slice $\binom{ [n]}{ k}$ of the hypercube $\{ 0,1\}^n$ is the set of all $n$-bit strings with Hamming weight $k$. We show that there exists a function on the balanced slice $\binom{ [n]}{ n/2}$ requiring $n - O(\log \log n)$ queries. We give an explicit function on the balanced slice requiring $n - O(\log n)$ queries based on independent sets in Johnson graphs. On the weight-2 slice, we show that hard functions are closely related to Ramsey graphs. Further we describe a simple way of transforming functions on the hypercube to functions on the balanced slice while preserving several complexity measures.
Categories: cs.CC math.CO