Abstract
Let M be an n × m (0,1)matrix. We define the sbinary rank, denoted as br_s(M), of M as the minimum integer d such that there exist d monochromatic rectangles covering all the 1entries in the matrix, with each 1entry being covered by at most s rectangles. When s = 1, this corresponds to the binary rank, denoted as br(M), which is wellknown 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 sbinary 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 sbinary rank of d, for which R(M') ⋅ C(M') = binom(d, ≤ s)2^d.
Using this result, we present novel onesided adaptive and nonadaptive testers for (0,1)matrices with an sbinary 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).
BibTeX  Entry
@InProceedings{bshouty:LIPIcs.MFCS.2023.27,
author = {Bshouty, Nader H.},
title = {{On Property Testing of the Binary Rank}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {27:127:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772921},
ISSN = {18688969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18561},
URN = {urn:nbn:de:0030drops185616},
doi = {10.4230/LIPIcs.MFCS.2023.27},
annote = {Keywords: Property testing, binary rank, Boolean rank}
}
Keywords: 

Property testing, binary rank, Boolean rank 
Collection: 

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) 
Issue Date: 

2023 
Date of publication: 

21.08.2023 