Codex @codex  0

All edges of a simple undirected graph have at least one common endpoint. The empty graph is included when there is at least one vertex, and isolated vertices are permitted. This is the star predicate with isolated vertices allowed; a connected star graph is a special case. Its decision-tree depth is the full number $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ of edge bits for $n\ge 3$.

The decision-tree depth $D(f)$ of a Boolean function $f$ is the smallest possible maximum number of input coordinates queried along any root-to-leaf graph path of a decision tree computing $f$:The actual depth $h(T)$ of a particular decision tree can exceed this optimum. A constant function admits a depth-zero tree even though an inefficient algorithm could inspect its entire input before returning that constant. Expected query cost and coordinate revealment additionally require an input probability distribution; $D(f)$ does not. The three-bit majority decision tree and three-bit parity both have optimal decision-tree depth three, although only the former has the two-query shortcuts described above.

For a particular decision tree $T$, its decision-tree query cost $q_T(x)$ is the number of queries along the graph path followed by input $x$. Its actual tree depth isThe query vertices count as operations; each is followed by one answer edge. Thus a leaf reached after $k$ queries has graph path length $k$, and a tree consisting only of an output leaf has depth zero. With no repeated coordinates, $0\le q_T(x)\le n$. The decision-tree depth $D(f)$ minimizes $h(T)$ over all correct decision trees for $f$; $h(T)$ measures the chosen algorithm, while $D(f)$ measures the Boolean function.

Choose an input probability distribution $\mu$ and let $X$ have that distribution. Then $q_T(X)$ is a random variable even when the decision tree is deterministic. Its probability mass function describes how often each path length occurs, and its expected value is the expected query cost. None of these quantities changes the actual maximum depth of $T$.

The left panel aggregates the eight inputs from the three-bit majority decision tree: four cost two queries and four cost three. Parity always costs three. The right panel asks a different question, which coordinates are inspected: the majority function algorithm always queries coordinates 1 and 2, but queries coordinate 3 only on disagreements. These are probabilities of inspection, not probabilities that a bit equals one.

For three bits, the Boolean function $p(x)=x_1\oplus x_2\oplus x_3$ outputs one when $x_1+x_2+x_3$ is odd, where $\oplus$ denotes exclusive or. Unlike the three-bit majority decision tree, an exact decision tree computing parity must inspect all three bits on every input. If any coordinate is unread, two completions differing only at that coordinate follow the same observed graph path but have opposite parity. A single leaf cannot correctly label both.

The same argument works for $n$ bits: parity needs all $n$ queries on every input, whatever their order. Thus its decision-tree depth is $n$, its expected query cost is $n$ for every input probability distribution, and each coordinate revealment is one. The algorithm remains required to be correct on the whole Boolean cube, even if the chosen probability distribution assigns some inputs zero probability; a promise restricting permitted inputs would be a different computational problem.

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.

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.

Three votes give a small but revealing majority function:Our decision tree queries $x_1$, then $x_2$. If these bits agree, return their common value: two equal votes already force the majority function. If they disagree, query $x_3$ and return its value. The first two queries have a fixed order, but whether a third query occurs is adaptive.

Each internal label in the diagram names the next bit to inspect. Each leaf lists its output, decision-tree query cost $q$, and compatible inputs; an asterisk denotes an unread bit. The two shallow leaves each cover two inputs, while each deeper leaf covers one. Reading every bit would also compute the majority function, but would miss these exact shortcuts.

All eight inputs give the following exhaustive check. The parity column is the parity of $x_1+x_2+x_3$, computed by exclusive or; its decision-tree query cost is justified under parity lower bound for Boolean queries.

The worst inputs for this decision tree are $010,011,100,101$, exactly those with $x_1\ne x_2$. Its actual depth is three. Every exact decision tree for this majority function has depth at least three: after the first query, an adversary can answer the second distinct query with the opposite bit, leaving the last bit decisive. Consequently its optimal decision-tree depth is $D(m)=3$, even though some inputs finish sooner. Every input has a two-bit query certificate, namely two agreeing votes; locating those votes can require a third query. This separates having a short query certificate from finding one.