Decision-tree adversary for a threshold function
= Decision-tree adversary for a threshold function
To prove that a threshold function requires every input bit in the worst case, an adversary answers queries while keeping completions on both sides of the threshold possible. If this remains true until the final unqueried bit, every decision tree has depth equal to the number of variables.