= Parity lower bound for Boolean queries
{title2=$D(\operatorname{PARITY}_n)=n$}
For three <bits>, the <Boolean function> $p(x)=x_1\mathbin\oplus x_2\mathbin\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>.
Back to article page
