Testing the Binary Rank with Polynomial Query Complexity

Abstract

We design an adaptive two-sided error testing algorithm for the binary rank of a $0,1$ matrix $M$ with query complexity $O(d^3\log (d+1)/{\epsilon }^2)$, where $d$ is the tested binary rank bound and $\epsilon$ is the distance parameter. This answers an open question posed by Parnas, Ron and Shraibman~\cite{parnas2021property}, who asked if the binary rank can be tested with query complexity polynomial in $d$ and $1/\epsilon$. Furthermore, our testing algorithm can be used to find an approximate binary decomposition of $M$ with an additional $d(n+m)$ queries. That is, under the promise that the binary rank of $M$ is at most $d$, we show how to find, with probability at least $5/6$, two $0,1$ matrices $A^{\prime },B^{\prime }$ such that $M^{\prime }=A^{\prime }\cdot B^{\prime }$ is a $0,1$ matrix which differs from $M$ on at most an $O(\epsilon )$ fraction of its entries. Our results also imply a testing algorithm with polynomial query complexity for the equivalent problem of testing if the edges of a bipartite graph can be partitioned into at most $d$ bicliques.