Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 1

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

In one standard form, the Håstad switching lemma says that if $F$ is a $k$-DNF and $\rho$ is a random restriction that independently leaves each variable unset with probability $p$ and otherwise assigns it a uniform Boolean value, thenThe dual statement exchanges DNF and CNF. Thus a small-width DNF becomes, with high probability, a shallow decision tree and hence a small-width CNF after a sufficiently sparse random restriction.

We use the following consequence of the Håstad switching lemma. If an unbounded-fan-in layered AND/OR circuit has depth $d$ and size $S$, then after $d-1$ successive independent random restrictions, each retaining a suitably small proportion $p=\Theta (1/\log S)$ of the currently live variables, the restricted circuit is constant on the leaves of a decision tree of bounded depth with probability at least $3/4$. To prove this switching-lemma depth reduction, first express the bottom layer as DNFs or CNFs, truncate any term wider than $O(\log S)$ because a random assignment satisfies or kills it except with probability $S^{-O(1)}$, and then apply the switching lemma with a union bound over at most $S$ gates. Replace each surviving bottom gate by its decision tree, switch DNF to CNF or conversely, and repeat. Choosing the constants so each round fails with probability at most $1/(4d)$ proves the claim by a union bound.

Suppose now that $S=\exp (o(n^{1/(d-1)}))$. After the $d-1$ rounds, the expected number of live variables isA Chernoff bound shows that at least $N/2$ variables remain live with probability tending to one. Conditional on the set of live variables, the assigned variables contain, with probability bounded away from zero, sufficiently close to half zeros and half ones that the restricted majority function remains a nonconstant threshold function on $\Omega (N)$ live variables. By part (i), its decision-tree depth is then $\Omega (N)$.

With positive probability both conclusions hold: the restricted circuit has bounded decision-tree depth, but the function it computes has depth tending to infinity. This contradiction provesFor each fixed depth, the constants in the reduction may be chosen uniformly to give an absolute positive constant after the usual depth convention is fixed.