3
$\begingroup$

I am interested in finding an efficient algorithm for the following problem:

Let $x \in [0,1]^n$ be some vector, with $x_n = 1$. We want to recover $x$, solely by asking queries of the form $\texttt{argmax}(x + v)$ where $v \in \mathbb{R}^n$ is an arbitrary additive shift.

A simple algorithm is to do binary search over each component of $x$ one-by-one. This requires $O(n \log 1/\epsilon)$ queries to recover $x$ up to precision $\epsilon$.

A more involved approach is to first sort $x$ (which can be done with $n$ queries) and then perform $n$ binary searches to find the gaps between adjacent elements. I believe this should give something like $O(n \log 1/(n\epsilon))$.

Is it possible to do better? My intuition is that it might be, as every query $i \gets \texttt{argmax}(x + v)$ gives us $\log_2 n$ bits of information. So in principle we could hope for an algorithm that uses $O(\frac{n \log 1/\epsilon}{\log_2 n})$ queries.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ One strategy that comes to mind: At each step, let $\mathcal{S}$ denote the set of all $x \in \mathbb{R}^n$ that are consistent with the responses to prior queries ($\mathcal{S}$ is the feasible region of a system of difference equations); sample $s$ randomly from $\mathcal{S}$; and let $v=-s$ and make a query with $v$. Heuristically, I suspect that the response to this query might be approximately uniformly distributed on $\{1,2,\dots,n\}$, hence convey $\lg n$ bits of information at each step. I have no bound or proof for worst-case number of queries. $\endgroup$
    – D.W. ♦
    Nov 15 at 19:55
  • 1
    $\begingroup$ Cross-posted mathoverflow.net/questions/458321/… $\endgroup$
    – David Roberts
    Nov 16 at 0:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.