Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 59 / 4

A decision tree queries individual input bits, chooses subsequent queries from previous answers and labels each leaf with an output. Its decision-tree depth is the largest number of queries on any root-to-leaf path; $D(f)$ is the least such depth over trees computing $f$. An evasive Boolean function on $n$ bits has $D(f)=n$.

Remove repeated queries along any path, since their answers are already known. A leaf at depth $r\le d<n$ fixes $r$ bits and leaves at least one bit free. The inputs reaching it form a subcube on which $f$ is constant, say $b$. Its contribution to the alternating sum isHere $\mathrm{wt}(x)$ is the Hamming weight. The leaf subcubes partition the input cube, so adding their contributions provesThe contrapositive is the alternating-sum criterion for decision-tree evasiveness: a nonzero alternating sum forces all $n$ bits to be necessary in the worst case.

Let $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ be the number of independent undirected-edge bits; use unordered pairs $i<j$. The paper's common-center graph property means that all present edges share a vertex. Isolated vertices are allowed, and the empty graph satisfies the property. This convention matters in the count.

The empty graph contributes $+1$ to the alternating sum. The $N$ one-edge graphs contribute $-N$. A graph with at least two edges and a common center has a unique center, since two different edges have just that common endpoint. For a fixed center, its possible edge sets are subsets of the $n-1$ incident edges. Their contribution after removing sets of size zero and one isThese graphs are counted once for each of their unique centers. Thus the alternating count of common-center graphs isPart (a) gives $D({\mathrm{STAR}}_n)\ge N$, while querying all $N$ bits always suffices. ThereforeThe relevant input length is $N$, not the number $n$ of graph vertices.

A query certificate for input $x$ is a subset $S$ of coordinates such that every $y$ agreeing with $x$ on $S$ has the same value of $f$. Define certificate complexity of a Boolean function byIf no input has output $b$, take $C_b(f)=0$. Unlike a decision tree, a query certificate may be selected with full knowledge of the input.

Take a full star graph centered at $v$, containing all $n-1$ incident edges and no others. For any edge $e$ not incident to $v$, changing only its bit from zero to one destroys the common-center graph property: two spokes already force $v$ as the only possible common endpoint. Therefore every positive query certificate for this input must include every nonincident edge bit, otherwise this one-bit change would preserve its answers but change the output. There are $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ such bits. Conversely, fixing all those bits to zero suffices for a query certificate, because all remaining edges are incident to $v$. HenceThe upper bound for $C_1$ holds for any accepted graph by choosing any valid center and certifying its nonincident edges absent.

For completeness, the negative side is much smaller. Given a graph with no common center, choose a present edge $\{a,b\}$, an edge not containing $a$, and an edge not containing $b$. These at most three present edges have empty common intersection and certify rejection. A triangle with isolated additional vertices needs all three of its present edges: with at most two queries, set every unqueried edge absent and the remaining present edges share a vertex. Thus the certificates for the common-center graph property satisfy