Metraipolis › archive › dc_55ea62b7655c

Streaming Algorithms for Monotonicity Testing — arXiv:2608.07073

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.07073
License (as archived)
CC0-1.0
Archived
2026-10-23T15:11:01.683Z
SHA-256 of the archived text
e0d14a35b76342990fd8f408bbb16ad9c773a6007dd441f2cfd9c16f5334c991
Stable URL of this page
https://metraipolis.com/documento/dc_55ea62b7655c

How to cite

Streaming Algorithms for Monotonicity Testing — arXiv:2608.07073 — arXiv (en), https://arxiv.org/abs/2608.07073 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_55ea62b7655c (Metraipolis archive dc_55ea62b7655c, sha256 e0d14a35b76342990fd8f408bbb16ad9c773a6007dd441f2cfd9c16f5334c991)
BibTeX
@misc{dc55ea62b7655c,
  title = {Streaming Algorithms for Monotonicity Testing — arXiv:2608.07073},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.07073},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_55ea62b7655c; sha256 e0d14a35b76342990fd8f408bbb16ad9c773a6007dd441f2cfd9c16f5334c991},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.07073. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Consider a poset - or equivalently an $n$-vertex DAG $G=(V, E)$ - and a boolean function $f: V \rightarrow \{0, 1\}$ on its vertex set. We say $f$ is monotone if $f(u) \leq f(v)$ for all $(u, v) \in E$. While there is extensive literature on the query complexity of testing monotonicity, we focus instead on the space complexity and initiate the study of this problem in the streaming setting. Namely, the edges of $G$ arrive in an arbitrary order, and the goal is to estimate distance to monotonicity of a given function $f$ using $\widetilde{O}(n)$ space. Note that while this space allows receiving and storing $f$, it is much smaller than the input graph $G$ which could have up to $\Omega(n^2)$ edges. Our main result is an algorithm that $(1+\epsilon)$-approximates distance to monotonicity in $\sqrt{n}^{1+o(1)}$ passes. We also prove that this is the best pass-complexity one can hope for, for any $O(1)$-approximation, short of improving the state-of-the-art streaming algorithm for $st$-reachability, which is a very well-studied problem. On the technical side, our algorithm approximates the size of maximum matching in (a subgraph of) the transitive closure of $G$. While the maximum matching problem has received significant attention in the streaming setting, the fact that we are computing it in the transitive closure requires very different ideas. In fact, a main contribution of our work is to connect sublinear time algorithms for estimating the maximum matching size to the streaming setting for the first time. While existing off-the-shelf sublinear time algorithms only result in an $n\sqrt{n}^{1+o(1)}$ pass algorithm in our setting, we show how to significantly improve upon them by allowing stronger queries (such as vertex and subset queries) that can be implemented just as efficiently as more standard adjacency matrix and list queries for our problem.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.07073 — 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-23T15:08:55.955Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).