= Solution
If $n=1$, return its sole index without a query. Otherwise first evaluate $f(t,t,\ldots,t)$ for $t=1,\ldots,d$ until two different outputs are found. Part i says these outputs are precisely $f_i(t)$, so two values $a,b$ with $f_i(a)\ne f_i(b)$ must exist. This uses at most $d$ calls to the <function-evaluation oracle>.
Maintain a candidate index <set> $S$, initially all indices. Split $S$ into two nearly equal pieces and choose one, $H$. Query the input that is $b$ on $H$ and $a$ everywhere else. Its output equals $f_i(b)$ exactly when $i\in H$, and otherwise equals $f_i(a)$. Retain the indicated half and repeat until one index remains.
The <loop invariant> is $i\in S$, and the witness outputs keep each test unambiguous. There are at most $\lceil\log_2 n\rceil$ splitting queries. The total is \b[at most $d+\lceil\log_2n\rceil$ evaluations], which is $O(d\log n)$ for $n\ge2$, and in fact a stronger additive bound. Only oracle calls are being counted; explicitly constructing each query vector can require $O(n)$ ordinary work. This is <identification of a unique essential variable>.
Back to article page
