Metraipolis › archive › dc_ca11eaa9a883
The Randomized Query Complexity of Finding Minimal Elements in Bounded-Width Posets — arXiv:2608.26981
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.26981
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T19:21:11.130Z
- SHA-256 of the archived text
0f535db85477855a9e849a9dd6d223d105c0ff2a16e45875531b0b15de8e3b64- Stable URL of this page
https://metraipolis.com/documento/dc_ca11eaa9a883
How to cite
The Randomized Query Complexity of Finding Minimal Elements in Bounded-Width Posets — arXiv:2608.26981 — arXiv (en), https://arxiv.org/abs/2608.26981 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ca11eaa9a883 (Metraipolis archive dc_ca11eaa9a883, sha256 0f535db85477855a9e849a9dd6d223d105c0ff2a16e45875531b0b15de8e3b64)
BibTeX
@misc{dcca11eaa9a883,
title = {The Randomized Query Complexity of Finding Minimal Elements in Bounded-Width Posets — arXiv:2608.26981},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.26981},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ca11eaa9a883; sha256 0f535db85477855a9e849a9dd6d223d105c0ff2a16e45875531b0b15de8e3b64},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.26981. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the zero-error randomized query complexity of finding all minimal elements in an unknown $n$-element poset of width at most $w$. Previous work of Daskalakis, Karp, Mossel, Riesenfeld, and Verbin established a randomized upper bound with leading term $\frac{w+1}{2}n$, while the corresponding lower bound left a multiplicative gap in the leading constant that approaches a factor of 2 as $w$ grows. We prove the finite lower bound \( R^{\mathrm{LV}}_{n,w}\ge \frac{w+1}{2}n-\frac{w(w+3)}4 +w\left(1-\frac1w\right)^n +\frac{w(w-1)}4\left(1-\frac2w\right)^n. \) Consequently, for every fixed $w$, \( R^{\mathrm{LV}}_{n,w} = \left(\frac{w+1}{2}+o(1)\right)n. \) Thus the known randomized upper bound has the correct asymptotic leading constant for every fixed width. The argument is based on a pairwise accounting of incomparable queries under a random-chain hard distribution, using a component-flip involution and a unique ownership property for incomparable comparisons. Generative AI was used in the preparation of this manuscript.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-28 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.26981 — 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-17T19:16:36.840Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).