Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-124/1/i/solution

Use the following decision-tree adversary for a threshold function. Regardless of which variables the tree queries, answer on the first queries and on the next queries. After any proper prefix of this answer sequence, the unqueried variables can be completed both to an input of weight below and to one of weight at least . Immediately before the last query the answers contain exactly zeros and ones, so the final bit alone determines the value of the threshold Boolean function . Thus every decision tree has a root-to-leaf path of length , while querying all variables gives depth . Hence

New to topics? Read the docs here!