Query complexity of Boolean functions on slices

Abstract

We study the deterministic query complexity of Boolean functions on slices of the hypercube. The $k^{th}$ slice $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ 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 $\left(\genfrac{}{}{0ex}{}{[n]}{n/2}\right)$ 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.