We present algorithms for testing if a $(0,1)$-matrix $M$ has Boolean/binary rank at most $d$, or is $epsilon$-far from Boolean/binary rank $d$ (i.e., at least an $epsilon$-fraction of the entries in $M$ must be modified so that it has rank at most $d$). The query complexity of our testing algorithm for the Boolean rank is $tilde{O}left(d^4/ epsilon^6right)$. For the binary rank we present a testing algorithm whose query complexity is $O(2^{2d}/epsilon)$. Both algorithms are $1$-sided error algorithms that always accept $M$ if it has Boolean/binary rank at most $d$, and reject with probability at least $2/3$ if $M$ is $epsilon$-far from Boolean/binary rank $d$.
تحميل البحث