I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem.

I am given access to an array of numbers. However, I am only allowed to query it by specifying an arbitrary subset of indices, in response to which I am then given the sum of the elements at those positions. These queries are quite costly, specifically they run in time $\tilde{O}(n^2)$ time (where $\tilde{O}(\cdot)$ hides polylogarithmic factors). I want to determine the element at each index in the array (i.e. reconstruct the array) using as little time as possible.

Of course, it is possible to do this by querying each element on its own. This algorithm does $n$ queries and hence has total running time $\tilde{O}(n^3)$. I am wondering if there is a faster way. Adaptivity does not help with this problem, so any algorithm would have two steps: First, it executes a fixed sequence of queries, and then reconstructs all elements using the query answers. Ideally, both steps run in time $o(n^3)$. So far, any set of $o(n)$ queries that I looked at makes recovery impossible. This might be the case for any such set of queries (and my intuition screams that this is probably the case), but I cannot see a proof for this.

I'd love an answer that either shows a faster algorithm or proves that $o(n)$ queries are impossible, but answers with partial insights would also be great.

  • 1
    $\begingroup$ The sums of the values at a subset of indices are linear functionals on the $n$-dimensional linear space of all arrays of length $n$. If you have less than $n$ of those linear functionals, and consider their outputs as tuples the range those tuples (the space of values that they output) will have linear dimension less than $n$. Therefore, a subset of positive dimension of the space of all arrays will return the value $0$ for all those functionals that you chose. So, you cannot tell them apart. $\endgroup$
    – plop
    Jul 26 '20 at 15:38
  • $\begingroup$ @plop Yes, you are absolutely right. In other words, any fixed set of queries forms a system of linear equations, and if you have less than $n$ queries then the equations are underdetermined. I should have seen this. If you want to post this as an answer, I will happily accept it. $\endgroup$
    – SmeltQuake
    Jul 26 '20 at 15:49

Your Answer

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

Browse other questions tagged or ask your own question.