Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 5 / d / ii / Solution

If $n=1$, return its sole index without a query. Otherwise first evaluate $f(t,t,\dots ,t)$ for $t=1,\dots ,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 at most $d+\lceil {\log }_{2}n\rceil$ evaluations, which is $O(d\log n)$ for $n\ge 2$, 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.