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?
An interesting question is (perhaps): What is the total expected time if we sample uniformly at random $\boldsymbol{r'}$ in $M$ until we have $\boldsymbol{r}'_j=\boldsymbol{r}_j$ for all $j \in S$? The question arises from the fact we cannot have, when $m$ is not too small, $d(\boldsymbol{r}_1^{\top}, \boldsymbol{r}_2^{\top}) \ll n$, for all pais of rows $\boldsymbol{r}_1$ and $\boldsymbol{r}_2$ in $M$, where $d$ is the hamming distance between two binary vectors. Hence, in the case $m$ is not too small, we could maybe leverage on the fact both $S$ and the sequence of row $\boldsymbol{r'}$ indices are sampled uniformly at random from $[n]$ and $[m]$ respectively.
