Alternating-sum criterion for decision-tree evasiveness
= Alternating-sum criterion for decision-tree evasiveness
{title2=$\sum_x(-1)^{\operatorname{wt}(x)}f(x)\ne0\Longrightarrow D(f)=n$}
A leaf reached before all $n$ input bits are queried leaves at least one coordinate free. Flipping that coordinate pairs its inputs with opposite alternating signs and equal output. Thus every such leaf contributes zero. If the total alternating sum is nonzero, a depth below $n$ is impossible.