Polynomial-query testing of binary rank

For a matrix $M\in\{0,1\}^{n\times m}$ , define its binary rank by $\operatorname{brank}(M)=\min\{d:\exists A\in\{0,1\}^{n\times d},\,B\in\{0,1\}^{d\times m}\text{ such that }M_{ij}=\bigvee_{k=1}^{d}(A_{ik}\wedge B_{kj})\text{ for all }i,j\}$ . Given query access to the entries of $M$ and parameters $d\in\mathbb{N}$ and $\epsilon>0$ , does there exist an adaptive or non-adaptive property tester with query complexity polynomial in $d$ and $1/\epsilon$ , independent of $n$ and $m$ , that distinguishes with constant success probability between: (i) $\operatorname{brank}(M)\le d$ ; and (ii) every matrix $M'$ with $\operatorname{brank}(M')\le d$ differs from $M$ in more than an $\epsilon$ fraction of its entries?

References

Primary source

arXiv

Additional references

Testing the Binary Rank with Polynomial Query Complexity — arXiv

Posted 3 weeks ago · edited 3 weeks ago

Progress summary

Refreshed 3 weeks ago

Claimed solved

A September 2026 unrefereed preprint claims to resolve the binary-rank testing question with a polynomial-query tester, but independent verification has not been found.

The problem asks whether binary rank can be tested with query complexity polynomial in the dimension and inverse error tolerance; it was posed by Parnas, Ron, and Shraibman. Earlier results did not settle this question.

Known results

One-sided non-adaptive testing used $O(2^{2d}/\epsilon^{2})$ queries.
One-sided adaptive testing used $O(2^{2d}/\epsilon)$ queries.
For fixed $s$ , later work improved $s$ -binary-rank bounds to approximately $\tilde{O}\!\left({d\choose\leq s}2^{d}/\epsilon\right)$ adaptively and $\tilde{O}\!\left({d\choose\leq s}2^{d}/\epsilon^{2}\right)$ non-adaptively, still exponential in $d$ .

September 2026 claimed resolution

The preprint Testing the Binary Rank with Polynomial Query Complexity claims a tester using $O(d^{3}\log(d+1)/\epsilon^{2})$ queries, together with recovery of an approximate binary decomposition. If correct, this answers the open query-complexity question, but the preprint is unrefereed and no independent verification was found.

Current status (as of September 2026): A polynomial-query tester is claimed in an unrefereed preprint, but the result remains unverified.

Sources

No solutions have been posted yet.