The Randomized Query Complexity of Finding Minimal Elements in Bounded-Width Posets

Luyao Fan, Jiayang Zou, Jiayang Gao +1

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,…