On Property Testing of the Binary Rank

Abstract

Let M be an n × m (0,1)-matrix. We define the s-binary rank, denoted as br_s(M), of M as the minimum integer d such that there exist d monochromatic rectangles covering all the 1-entries in the matrix, with each 1-entry being covered by at most s rectangles. When s = 1, this corresponds to the binary rank, denoted as br(M), which is well-known in the literature and has many applications.
Let R(M) and C(M) denote the sets of rows and columns of M, respectively. Using the result of Sgall [Jiří Sgall, 1999], we establish that if M has an s-binary rank at most d, then |R(M)| ⋅ |C(M)| ≤ binom(d, ≤ s)2^d, where binom(d, ≤ s) = ∑_{i=0}^s binom(d,i). This bound is tight, meaning that there exists a matrix M' with an s-binary rank of d, for which |R(M')| ⋅ |C(M')| = binom(d, ≤ s)2^d.
Using this result, we present novel one-sided adaptive and non-adaptive testers for (0,1)-matrices with an s-binary rank at most d (and exactly d). These testers require Õ(binom(d, ≤ s)2^d/ε) and Õ(binom(d, ≤ s)2^d/ε²) queries, respectively.
For a fixed s, this improves upon the query complexity of the tester proposed by Parnas et al. in [Michal Parnas et al., 2021] by a factor of Θ(2^d).