cs.DSNov 10, 2026
SaveNonadaptive One-Sided Testing of Binary Rank
Organizations: Faculty of Computer Science, Technion Israel Institute of Technology
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 , with one-sided error and nonadaptive queries. We give a tester using queries, independent of the matrix dimensions and a general lower bound of .
Figures & tables
| Upper-bound source | Model | Queries |
|---|---|---|
| Nakar–Ron [ 4 , 5 ] | Nonadaptive, one-sided | |
| Parnas–Ron–Shraibman [ 5 ] | Nonadaptive, one-sided | |
| Bshouty [ 2 ] | Nonadaptive, one-sided | |
| Parnas [ 7 ] | Adaptive, two-sided | |
| Theorem 3.4 | Nonadaptive, one-sided |
Table 1: Selected upper bounds for binary rank at most . The models differ as indicated.
| Result | Query complexity |
|---|---|
| Upper bound (Theorem 3.4 ) | |
| Lower bound (Theorem 5.3 ) |
Table 2: General nonadaptive one-sided testing of binary rank at most .