1
$\begingroup$

Imagine this game. I pick a permutation $p$ of $1..n$ and give you an oracle. When the oracle is queried with any sequence of $n$ numbers $\in 1..n$, it masks each number by applying some unknown bijection $f$ and then permutes the masked values using $p$. Your goal is to repeatedly query the oracle to recover $p$ with as few queries as possible.

A $\theta(\log(n))$ solution is obvious. First query $1, 2, 3, 4, \ldots$ and $2, 1, 4, 3, \ldots$, the second query reversing each of the $\lfloor \frac{n}{2} \rfloor$ pairs. As swapping a pair in the input swaps the corresponding pair in the output, we identify the $\lfloor \frac{n}{2} \rfloor$ pairs that they map to, albeit with unknown correspondence. (If $n$ is odd, the $n$th item is the one remaining in place so $p(n)$ is known.) Then query $1, 1, 3, 3, \ldots$ to identify which item in each output pair corresponds to the first item of an input pair. With 3 queries we have reduced the problem to one of size $\lfloor \frac{n}{2} \rfloor$ by querying from now on with identical pairs of items; recurse. We use $3\log n \pm O(1)$ queries.

Can we do better? For example, is there a strategy using $\log n \pm O(1)$ queries?

Regarding lower bounds, if $q$ queries is optimal for $\frac{n}{2}$ we can run the strategy twice in parallel, side-by-side, in $q$ queries for $n$ but we still lack information about which $\frac{n}{2}$ of the input maps to the corresponding $\frac{n}{2}$ elements of the output, suggesting we need at least one additional query for $n$. This argument seems to imply $\Omega(\log(n))$ query complexity - can it be made rigorous?

$\endgroup$
2
$\begingroup$

Suppose that my input is some permutation $\sigma$. Applying $f$ is the same as multiplying by $f$ from the left (assuming that $\alpha\beta(i) = \alpha(\beta(i))$, and then applying $p$ is the same as multiplying by $p$ from the right. In other words, we have an oracle for the function $\sigma \mapsto f\sigma p$.

Given $f\sigma p$ and $f\tau p$, we can find $(f\sigma p)^{-1} (f \tau p) = p^{-1} (\sigma^{-1} \tau) p$. In particular, using two oracle calls we can find $p^{-1} (1\;2\;3\;\cdots\;n) p = (p^{-1}(1)\;p^{-1}(2)\;p^{-1}(3)\;\cdots\;p^{-1}(n))$. Using one more oracle call, we can also find $(p^{-1}(2)\;p^{-1}(1)\;p^{-1}(3)\;\cdots\;p^{-1}(n))$ (the only difference is the first two values). From these two long cycles we can locate $p^{-1}(1)$ and so recover $p^{-1}$ (and so $p$), as well as $f$ if we so wish. In total, we used three oracle calls.

$\endgroup$
  • $\begingroup$ Great. So this shows that we can leverage a fixed fraction of the $n \log n$ bits of "information" in the input to decode the $n \log n$ hidden bits. $\endgroup$ – Solomonoff's Secret Mar 28 '18 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.