2
$\begingroup$

Alice has a matrix $A \in \{0,1\}^{n \times m}$ such that the sum of each row is $1$. Bob tries to find the indices of the ones (he knows that the sum of each row is $1$). The type of questions Bob can ask Alice is: "Does $\sum a_{i,j} = 0$" for some subset $\{a_{i,j}\}$ of size $n$. How fast (i.e. minimum questions) can Bob recover the ones (even with high probability)?

$\endgroup$
1
  • 1
    $\begingroup$ Do you have any thoughts on the question? $\endgroup$ – Yuval Filmus Mar 22 '20 at 21:27
2
$\begingroup$

Let me consider the case $n = m$ for concreteness. Since the entropy of $A$ is $n\log n$ and each question results in at most one bit of information, at least $n\log n$ queries are needed.

Suppose that a question is selected uniformly at random. The probability that the answer is zero is $(1-1/n)^n \approx 1/e$, and in that case, we can mark all the queried entries as zero. Imagine making such queries until $N$ are successful. This is the same as making $N$ queries, each of which involves $n$ zero positions at random. The probability that a particular zero position is never queried is $$ \left(1 - \frac{n}{n(n-1)}\right)^N \approx e^{-N/n}. $$ Therefore after $(2+\epsilon) n\log n$ queries, the probability that a particular zero position is never queried is at most roughly $n^{-2-\epsilon}$, and so the probability that not all zero positions are revealed is at most $n^{-\epsilon}$. We conclude that $(2e+\epsilon) n\log n$ queries suffice to reveal the matrix with probability $1-o(1)$.

We can repeat the calculation for general $m$, but the bounds no longer match. For example, when $m$ is very large, the answer to most questions will be zero, and so bounding the amount of information obtained from a single query by one bit is too generous.

$\endgroup$

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.