Identification of a unique essential variable ($d+\lceil {\log }_{2}n\rceil \text{ queries suffice}$)

Suppose an unknown function on $\{1,\dots ,d{\}}^n$ has exactly one essential variable. Query the diagonal inputs $(t,\dots ,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 }_{2}n\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 }_{2}n\rceil$. Integer outputs in the unrestricted problem need not be binary; the restricted family is what makes this query complexity argument valid.