Metraipolis › archive › dc_328dc3463dfe
Testing the Binary Rank with Polynomial Query Complexity — arXiv:2609.10496
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.10496
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T11:17:58.859Z
- SHA-256 of the archived text
4aaef696757bfbf24acdbdbee150220a04a3a31687fe9e83b0b8bcb98b04c596- Stable URL of this page
https://metraipolis.com/documento/dc_328dc3463dfe
How to cite
Testing the Binary Rank with Polynomial Query Complexity — arXiv:2609.10496 — arXiv (en), https://arxiv.org/abs/2609.10496 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_328dc3463dfe (Metraipolis archive dc_328dc3463dfe, sha256 4aaef696757bfbf24acdbdbee150220a04a3a31687fe9e83b0b8bcb98b04c596)
BibTeX
@misc{dc328dc3463dfe,
title = {Testing the Binary Rank with Polynomial Query Complexity — arXiv:2609.10496},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.10496},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_328dc3463dfe; sha256 4aaef696757bfbf24acdbdbee150220a04a3a31687fe9e83b0b8bcb98b04c596},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.10496. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We design an adaptive two-sided error testing algorithm for the binary rank of a $0,1$ matrix $M$ with query complexity $O(d^3\log(d+1)/\epsilon^2)$, where $d$ is the tested binary rank bound and $\epsilon$ is the distance parameter. This answers an open question posed by Parnas, Ron and Shraibman~\cite{parnas2021property}, who asked if the binary rank can be tested with query complexity polynomial in $d$ and $1/\epsilon$. Furthermore, our testing algorithm can be used to find an approximate binary decomposition of $M$ with an additional $d(n+m)$ queries. That is, under the promise that the binary rank of $M$ is at most $d$, we show how to find, with probability at least $5/6$, two $0,1$ matrices $A',B'$ such that $M' = A' \cdot B'$ is a $0,1$ matrix which differs from $M$ on at most an $O(\epsilon)$ fraction of its entries. Our results also imply a testing algorithm with polynomial query complexity for the equivalent problem of testing if the edges of a bipartite graph can be partitioned into at most $d$ bicliques.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.10496 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T10:56:12.726Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).