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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Mar 3, 2018 at 0:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .