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

If coordinate $j$ is not an essential variable of a function, changing that coordinate alone never changes the output, for any values of the other coordinates. Take two inputs with the same $i$-th coordinate. Change their other coordinates one at a time to transform the first input into the second. Every such change is inessential, so all intermediate outputs are equal.

Define $f_i(t)=f(1,\dots ,1,t,1,\dots ,1)$, with $t$ in position $i$. The preceding argument gives $f(x_1,\dots ,x_n)=f_i(x_i)$. Since $i$ is essential, $f_i$ is nonconstant. The conclusion depends on the full “for every context” negation of essentiality, not merely on testing a coordinate at one selected input.

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.

Restrict the unknown function to the $n$ possibilities $f^{(i)}(x)=1$ if $x_i=1$, and $2$ otherwise. Each has exactly one essential variable, even if the allowed alphabet has more than two values. Every oracle answer in this restricted family is one bit.

A correct adaptive deterministic algorithm must distinguish all $n$ possibilities. A binary decision tree of depth $q$ has at most $2^q$ leaves, so $2^q\ge n$. Therefore $q\ge \lceil {\log }_{2}n\rceil =\Omega (\log n)$. Restricting the answer family is essential to the argument: unrestricted integer-valued answers need not have binary branching. Combined with part ii, this gives optimal logarithmic query complexity for fixed $d$.