  We study the query complexity of slices of Boolean functions. Among other
results we show that there exists a Boolean function for which we need to query
all but 7 input bits to compute its value, even if we know beforehand that the
number of 0's and 1's in the input are the same, i.e. when our input is from
the middle slice. This answers a question of Byramji. Our proof is
non-constructive, but we also propose a concrete candidate function that might
have the above property. Our results are related to certain natural discrepancy
type questions that -- somewhat surprisingly -- have not been studied before.

Combinatorics;Computational Complexity