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:

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}$.

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$.

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?

exactsearch 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 '18 at 9:47