Algorithm tests binary rank of matrices with fewer queries

Testing the Binary Rank with Polynomial Query Complexity

Data Structures and AlgorithmsDiscrete Mathematics

Summary

Figuring out the complexity of a matrix made of zeros and ones is a tricky problem. The authors created a new method that can quickly check if the matrix’s binary rank is below a certain limit. Their method works by only looking at a small part of the matrix, rather than the entire thing. If the matrix fits the limit, the method can also help build a close approximation of it.

What this means in practice

Authors

Michal Parnas

Abstract

We provide 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)/ε^2)$, where $d$ is the tested binary rank bound and $ε$ is the distance parameter. This answers an open question posed by Parnas, Ron and Shraibman~\cite{parnas2021property}, who asked whether the binary rank can be tested with query complexity polynomial in $d$ and $1/ε$. 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',B'$ such that $M' = A' \cdot B'$ is a $0,1$ matrix which differs from $M$ on at most an $O(ε)$ fraction of its entries.