Median Selection with  Noisy  and Structural Information
Mingyu Kang, Chenglin Fan
We study the problem of computing the exact median using unreliable comparison oracles, motivated by settings such as crowdsourced or noisy decision-making. We analyze the complexity of this problem under both the classical and partially ordered input settings. In the classical setting, we introduce a modified LazySelect algorithm that combines weak comparisons with occasional strong comparisons through majority voting. We show that this hybrid strategy has near-linear running time and can achieve high-probability correctness using only sublinear strong comparisons, even when the weak oracle is only slightly better than random guessing.  Our theoretical results hold under the persistent comparison model, where resampling will not amplify the probability of correctness. In the partially ordered setting, we generalize the notion of median to directed acyclic graphs (DAGs) and show that the complexity of median selection depends heavily on the DAG's width. We complement our analysis with extensive experiments on synthetic data.