The Randomized Query Complexity of Finding Minimal Elements in Bounded-Width Posets
TL;DR
The known randomized upper bound has the correct asymptotic leading constant for every fixed width, based on a pairwise accounting of incomparable queries under a random-chain hard distribution and a unique ownership property for incomparable comparisons.
Abstract
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.