4
$\begingroup$

Let $M \in \{0,1\}^{m\times n}$, where $n\gg 1$ and $m\le n$. A procedure consisting of the following three steps is repeated $t\gg 1$ times:

  1. A row $\require{amsmath} \boldsymbol{r}$ of $M$ picked in an adversarial (hidden) way, viz. we do not know the row index of $\boldsymbol{r}$.

  2. We receive a set $S$ formed by sampling uniformly at random $\sqrt{n}$ indices from $[n]$ and the sequence of all values $r_i$ for all $i \in S$.

  3. We need to find at least one row $\boldsymbol{r}'$ of $M$ such that, for all column indices $j \in S$, we have $\boldsymbol{r}'_j=\boldsymbol{r}_j$.

It is easy to see that the simplest method to accomplish this task requires in the worst case a total number of elementary operations (e.g., verifying if two binary digits are equal) that is order of $t\,m\,\sqrt{n}$, as both $t$ and $n$ approach infinity.

Question: Is there a (perhaps randomized) method to accomplish this task such that, by suitably pre-processing in polynomial (in $n$) time the matrix $M$ in a preliminary phase if necessary, the (expected) number of elementary operations is equal in the worst case to $o(t\,m\,\sqrt{n})$?

For example, consider we pre-process the matrix $M$ by permutating its rows such that, if $N_i$ is the integer corresponding to the binary digit representation of the $i$-th row of $M$, they are sorted in such a way $N_i\le N_j$ whenever $i \le j$. Is there any method able to take advantage of this row (sorting) permutation?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ An answer that matches the letter, but presumably not the spirit, of your question is to do so much preprocessing that all possible questions have been answered already and stored in a convenient table. Or you can go part way by, say, making a table that allows any $n^{1/4}$ columns of $M$ to be looked up immediately. To make the question more useful, I think you need to put some limit on either the time used for preprocessing or the space used to hold the results of preprocessing. $\endgroup$
    – Brendan McKay
    Mar 2, 2018 at 2:25
  • 1
    $\begingroup$ Having matrix rows sorted (in lexicographic order) allows to perform exact search of $r$ in $M$ in time about $\log_2(m)n$, which may be better than $m\sqrt{n}$ (depending on relationship between $m$ and $n$). $\endgroup$
    – Max Alekseyev
    Mar 2, 2018 at 9:47
  • $\begingroup$ Brendan, thank you. You are right about defining the pre-processing time complexity bound. I would just say that a polynomial (in n and m) time and space complexity for the preprocessing is OK. About the table, I don't think it can work, because the number of columns that can be sampled from a subset of $n^{1/4}$ columns is exponential in $n$ (it is still exponential $n$ if we consider the expected number of columns sampled by any fixed subset of $n^{1/4}$ columns). I instead believe it would be interesting to analyse the expected time required by verifying u.a.r. each row until finding $r'$. $\endgroup$
    – Penelope Benenati
    Mar 2, 2018 at 17:00
  • $\begingroup$ Max, thank you for your answer. What you say it is clear, but in my problem I took for granted that you have access only to $\sqrt{n}$ elements of the copy of $\boldsymbol{r}$ you receive in step 1. And, of course, as you know even if the $n$-dimensional matrix row vectors are sorted in $M$, the rows of a submatrix obtained by sampling u.a.r. $\sqrt{n}$ from $M$ are not sorted in general. Hence, it is no possible in general to apply dichotomic search methods. I am now rephrasing the problem in order to avoid misunderstanding. Thank you again. $\endgroup$
    – Penelope Benenati
    Mar 2, 2018 at 17:14

1 Answer 1

Reset to default
1
$\begingroup$

This answer shows maybe. Pick a parameter $s$. We will precompute $2n$ Bloom filters with false positive rate $s$ and size $g(s)$ such that $B_{i,0}$, $B_{i,1}$ such that $k \in B_{i,b}$ if $m_{i,k}=b$. This takes time $O(g(s)mn)$ Our algorithm is as follows: we will intersect the $\sqrt{n}$ bloom filters (time $O(g(s)\sqrt{n})$) and then look within in that set for the answer. This takes time $O((1+s)\sqrt{n})$

Total time for $t$ operations is $O(g(s)mn+t(g(s)+1+s)\sqrt{n})$. If you can pick a better $s$ for $t$, then yes.

Why is the false positive rate not larger for the intersection? Because the intersection of the Bloom filters is exactly the Bloom filter of the intersection. I don't think the adversary can do much about picking the worst row, but that takes some more analysis.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, this seems an interesting approach. However, I would need some days to calculate the false positive rate in the worst case. $\endgroup$
    – Penelope Benenati
    Mar 3, 2018 at 0:48

Your Answer

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

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