paper
arXiv cs.LG
November 11th, 2026 at 5:00 AMNonadaptive 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