Prefer a chat interface with context about you and your work?
Query Complexity of Boolean Functions on the Middle Slice of the Cube
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 …