= Identification of a unique essential variable
{title2=$d+\lceil\log_2n\rceil\text{ queries suffice}$}
Suppose an unknown <function> on $\{1,\ldots,d\}^n$ has exactly one <essential variable>. Query the diagonal inputs $(t,\ldots,t)$ to find two coordinates values $a,b$ giving distinct outputs; at most $d$ <function-evaluation oracle> calls suffice because the unary dependence is nonconstant. A query taking value $b$ on an index subset $H$ and $a$ outside it then tests whether the essential coordinate lies in $H$. Repeated halving locates it in at most $\lceil\log_2n\rceil$ further queries. If $n=1$, no query is needed.
For a matching lower bound with fixed $d$, restrict to $f^{(i)}(x)=1$ when $x_i=1$ and $2$ otherwise. Every query has only two possible replies. A binary <decision tree> distinguishing the $n$ possible essential indices needs at least $n$ leaves and depth $\lceil\log_2n\rceil$. <Integer> outputs in the unrestricted problem need not be binary; the restricted family is what makes this <query complexity> argument valid.
Back to article page
