Source-linked AI summary
The Randomized Query Complexity of Finding Minimal Elements in Bounded-Width Posets
Luyao Fan, Jiayang Zou, Jiayang Gao, Jia Wang
TL;DR
The paper studies determining minimal elements in bounded-width posets and addresses a gap between prior randomized upper and lower bounds. It proves the lower bound in Theorem 1 using a random-chain distribution and component-based arguments.
Problem
The task is to determine minimal elements in bounded-width posets, while prior work left a gap between randomized upper- and lower-bound leading constants.
Method
The proof uses a hard distribution whose realizations are unions of at most w chains, together with equiprobable labeled color assignments, component flips, and transcript-preserving arguments.
Results
The argument establishes the lower bound in Theorem 1 by showing that some legal poset satisfies the required expected-query lower bound.
Takeaways & Limitations
For every fixed w, the paper concludes its stated asymptotic result, improving the prior lower-bound comparison as w grows.
Takeaways & Limitations
The hard-distribution construction is restricted to realizations that are disjoint unions of at most w chains, ensuring width at most w.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies finding all minimal elements in an unknown poset promised to have width at most w. It closes the prior randomized lower-bound gap, showing the known upper bound has the correct asymptotic leading constant for every fixed width.
- The task is to determine all minimal elements using comparison queries under the promise width(P) ≤ w.
- Prior work gave a Las Vegas algorithm using (w+1)n/2 + O_w(log n) expected queries for fixed w.
- The prior randomized lower bound had leading term (w+3)n/4, leaving an upper-to-lower leading-constant ratio of 2(w+1)/(w+3).
2 Model and hard distribution
The model asks exact algorithms to identify minimal elements through comparison queries, and the lower bound uses a random-chain distribution supported on posets of width at most w.
- A deterministic exact algorithm must terminate and output Min(P) on every legal input.
- The hard distribution independently assigns colors and chooses a uniformly random permutation of the vertices.
- Every realization is a disjoint union of at most w chains, hence has width at most w.
- For a fixed deterministic algorithm, N and N∥ count comparable and incomparable query answers, respectively.
3 Comparable queries
Comparable queries are charged through witnesses for nonminimal vertices, yielding a direct accounting of the comparable answers required by exactness.
- If x is nonminimal, exactness requires querying some pair that returns a witness y ≺ x before termination.
- The witness argument works by moving x earlier within its color class, which makes x minimal without changing the prior transcript.
- There are n − K nonminimal vertices, and each is the larger endpoint of at least one comparable query.
4 Incomparable queries
The incomparable-query analysis pairs executions under component flips, counts incomparable external merges, and assigns each incomparable physical query to at most one color pair.
- Pairwise accounting: For a color pair {a,b}, the pair-query graph connects vertices in S_ab whenever the algorithm queries them.
- Pairwise accounting: An external merge queries endpoints in distinct connected components of the current pair-query graph.
- Component-flip pairing: The component-flip involution preserves the algorithm's transcript and decision-tree node while swapping comparable and incomparable outcomes.
- Terminal connectivity: If M_ab > 0, terminal connectivity forces the terminal pair-query graph G_ab to be connected.
- Pair charge: Starting with m components and ending with one gives exactly m−1 external merges for a nonempty pair.
- Pair charge: Exactly half of external-merge occurrences are incomparable, and unique ownership ensures each incomparable physical query is charged to at most one unordered color pair.
5 Proof of the main theorem
The proof converts Las Vegas randomized algorithms into exact deterministic algorithms for almost every random seed, then averages query costs to establish the lower bound.
- Proof of the main theorem: The proof combines earlier inequalities to show that every deterministic exact algorithm satisfies the required lower-bound constraint.This deterministic statement is the ingredient transferred to Las Vegas algorithms through the random-seed argument.
- Proof of the main theorem: A Las Vegas algorithm is fixed at a random seed to obtain a deterministic algorithm whose query count is Q(P, r).The Las Vegas property guarantees termination and correctness on every legal input with probability one.
- Proof of the main theorem: For almost every random seed, the fixed-seed algorithm is exact on every legal poset because the input family is finite.A single null set of seeds can be excluded simultaneously across all legal inputs.
- Proof of the main theorem: Averaging over the internal randomness yields a legal poset P* with expected query cost at least L_n,w, and taking the infimum proves Theorem 1.The averaging step uses Tonelli’s theorem.
AI Assistance
Generative AI was used during preparation of the manuscript.
- AI Assistance: Generative AI was used in preparing the manuscript.
- AI Assistance: The manuscript reports generative-AI assistance as part of its preparation process.
- AI Assistance: AI use is disclosed in the manuscript’s preparation statement.