License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.27
URN: urn:nbn:de:0030-drops-185616
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18561/
Bshouty, Nader H.
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).
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:1--27:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-292-1},
ISSN = {1868-8969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18561},
URN = {urn:nbn:de:0030-drops-185616},
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 |
