= Classical query complexity of linear Boolean function identification
{title2=$D(n)=n$}
In exact classical identification of an unknown <linear Boolean function> $f_a(x)=a\cdot x$, a <function oracle> call returns one <bit> $f_a(x)$. The <query complexity> is exactly $n$ for $n\ge1$. Queries on the <standard basis> inputs $e_j$ reveal $a_j$, proving sufficiency. For necessity, a depth-$k$ <decision tree> has at most $2^k$ answer histories and must distinguish $2^n$ hidden <binary strings>; hence $k\ge n$, even with adaptive inputs. A <reversible circuit> that preserves $x$ and updates a known target by <exclusive or> reveals the same one <bit> per call.
There is also a useful <linear algebra> proof. Along a fixed history, the chosen inputs form the rows of a <matrix> $M$ over the two-element <finite field>, and the replies specify $Ma$. If there are $k<n$ queries, the <rank-nullity theorem> gives a nonzero <vector> $v$ with $Mv=0$. Then $a$ and $a+v$ give identical replies throughout this history. This also explains why adaptive choices cannot evade the bound: equal earlier replies force the same later choices.
Back to article page
