paper
arXiv cs.LG
November 11th, 2026 at 5:00 AM

Nonadaptive One-Sided Testing of Binary Rank

arXiv:2611.14163v1 Announce Type: cross Abstract: The binary rank of a binary matrix is the minimum number of disjoint all-one rectangles that partition its one-entries. We study entry-query testing of binary rank at most $d$, with one-sided error and nonadaptive queries. We give a tester using $\tilde O(d^4/\epsilon^2)$ queries, independent of the matrix dimensions and a general lower bound of $\tilde \Omega(d^{3/2}/\epsilon)$.

#research

Get stories like this every Monday

The week's most important AI news in one email. Free, unsubscribe anytime.

Score: 3.15

Engagement proxy: 0

Canonical link: https://arxiv.org/abs/2611.14163