Binary rank of zero one matrices tested efficiently with few queries
Testing the Binary Rank with Polynomial Query Complexity
Data Structures and AlgorithmsDiscrete Mathematics
Summary
Knowing the binary rank of a matrix made up of zeros and ones helps understand its complexity. The authors present a method to quickly check if a matrix has a binary rank up to a given number by looking at only a small part of the matrix. Their approach uses a number of queries that grows reasonably with the rank and the accuracy needed. They also show how to find a simple approximation of the matrix based on this binary rank using slightly more queries. This work solves a previously open question about how efficiently this property can be tested.
binary rankzero one matrixproperty testingquery complexityadaptive algorithmapproximate matrix decompositiontwo sided errordistance parameter
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.