Median Selection with  Noisy  and Structural Information
Authors: Chenglin Fan
Mingyu Kang
Venue: NeurIPS 2025 poster ()
Keywords: median selection
unreliable oracles
persistent comparison model
lazy select algorithm
partially ordered data
Primary area: theory
TL;DR: This paper studies exact median selection with unreliable oracles, proposing a hybrid algorithm with sublinear strong comparison cost under the persistent model.

Abstract: We study the problem of computing the exact median by leveraging side information to minimize costly, exact comparisons. 
We analyze this problem in two key settings: 
(1) using predictions from unreliable 'weak' oracles, and 
(2) exploiting known structural information in the form of a partial order. 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.

Median Selection with Noisy and Structural Information
Chenglin Fan"
Mingyu Kang" Scoul National University Scoul 08826, South Korea mgmh260smu. ac .kr
Scoul National University Scoul 08826, South Korea f Fanchengl in@suu. ac kr
Abstract
We study the problem of computing the exact median by leveraging side information to minimize costly, exact comparisons.
analyze this problem two key settings: (1) using predictions from unreliable "weak" oracles, and (2) exploiting known structural information in the form a partial order. the classical setting, we introduce 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-prole high-rrobability 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, generalize the notion of median 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.
Introduction
Median selection a fundamental problem in algorithm design, with wide-ranging applications in machine learning, data analysis, and decision-making. Given set of elements with an unknown total order, the goal is to identify the median-the element of rank [n/2].. Finding the median of set is classical problem in computer science and statistics, with applications ranging from robust statistics to machine learning and decision-making The traditional model assumes that comparisons perfect and equally costly, but in many modern settings- such crowdsourcing [Karger et al.) 2011], preference elicitation [Lu and Boutilier 2011). or federated analytics [Kairouz et al. 2021 comparisons can be noisy, expensive, even unreliable.
Our work addresses these challenges through a unified framework in which side information is leveraged to reduce reliance expensive, definitive comparisons. We consider two forms of side information: predictions from a cheap but noisy "weak" oracle, and structural knowledge in the form of a pre-existing partial order. The latter can be viewed the outcomes of trusted, historical comparisons, framing both settings as instances of a common problem: how to efficiently compute the median when partial imperfect comparison information already available. This setting is motivated by recent work
caarning-augmenter algorithms [Lykouris and Vassilvitski] 2021 Purohit et al. 2018), which aim to bridge the gap between traditional worst-case algorithms and data-driven approaches.
key insight is that in many practical scenarios, the elements to be compared may already have some latent structure. For example, partially ordered sets or when the input items are embedded
Authors listed alphabetically, All authors contributed equally to this work.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

in known hierarchy, some comparisons may be inferred or ruled out. Exploiting such structural properties has proven useful in sorting and selection [Daskalakis al. 2011].
We formalize this intuition and present two main algorithmic results: (1) when weak comparisons available with some bias toward the correct order, we show how to combine them with small number of strong comparisons to recover the median; (2) when the input set has known partial order (e.g., a DAG), we show how to use the structure reduce the number of strong comparisons to sublinear, while ensuring correctness. Our results are accompanied by theoretical bounds and suggest new paradigm for combining structural priors and learning predictions in classic decision problems.
1.1 Related Works
1.1.1
State-of-the-Art Algorithms for Finding the Median
There exist two main classes of median selection algorithms: randomized algorithms and defermin- istic algorithms.
Randomized Algorithms
QuickSelect: A randomized variant of QuickSort [Hoare 1961] J. QuickSelect randomly
selects a pivot and partitions the array, recursively narrowing down to the median. Its expected time complexity is (n), but in the worst case, it can be O(n²) with unlucky pivots.
LazySelect: Known as Rivest and Floyd's Select algorithm (Floyd and Rivest 1975). LazySelect samples r elements, selects two pivots from the sorted sample, and partitions the array into three regions. It sorts the middle region and returns the median. It runs in expected linear time with high probability, achieving O(n) with probability 1 O(n V1).
Deterministic Algorithms
Sorting-Bass -Baeed Approach: A simple deterministic method involves sorting the array (e.g.. MergeSort, HeapSort) [Cormen et al., 2022 and selecting the middle element. Its worst-case complexity is On log n), making inefficient for large datasets.
Median of Medians [Blum et al. 1973] To improve QuickSelect's worst-case perfor- mance, this algorithm deterministically selects pivot in O(n) time, ensuring a worst-case complexity of O(n).
1.1.2 Learning-Augmented Algorithms
Recent advancements in machine learning have inspired auggmentd algorithms, which leverage additional probabilistic information to enhance traditional algorithms. Learning-augmentte algorithms do not rely solely on standard comparisons but instead incorporate predictions that guide the selection process. This paradigm is particularly useful when comparisons have different costs or reliability levels, as in the case of strong and weak comparison oracles.
augmented algorithms have been successfully applied in various domains, including:
Algorithms with Predictions. While much of the prior research focuses on online settings
such caching [Lykouris and Vitsilvitskii 202T Rohatgi 2020 Bansal et al. 2022
rent-or-buy problems [Purohit et al.] Angelopoulos et al. 2024 and scheduling Azar
jtt al. 2021 Lindermayr and Megow| 20022. recent advancements have extended these
techniques to offline problems. Notable examples include matching [Dinitz et al.) 2021
clustering [Ergun et al. 202T], and sorting (Bai and Coester 2023 Lu al.) 2021] Inspired
by Kraska et al. 2018 several studies also examine data structures Lin et al.) 2022 and
robust use of multiple predictors [[nand et al. [022] Antoniadis al.) 2023]. Recent works continue to broaden the field's reach: binary search with distributional predictions (Dinitz let al. 2024), competitive warm-start strategies for algorithms with predictions [Blum
and Srinivas 2025 dynamic graph algorithms with predictions [Brand et al. 2024]. and
serming-auggmnted priority queues [Benomar and Coester 2024 highlight the versatility of predictions in diverse algorithmic domains.

---

Sorting with Prediction. Lu et al. [021] studied generalized sorting with forbidden comparisons and prediction errors similar our weak comparisons, achieving bounds of (n log + w) and O(ncc) though the latter degrades to O(n²) with one error per item-ours remains On)). Erlebach et al. [2023] explored sorting and hypergraph orienta- tion under uncertainty with predictions, aiming to mínimize the number of queries. [Bai and Coester [2023] proposed
sorting algorithms using predicted positions and fast-but-noisy comparisons, achieving optimal O (2, log 1R) exact comparisons ( 77 denote the prediction error of the rank of i-th element), which degrades smoothly from (n)) to (n log n) prediction error increases.
1.1.3 Sorting with Structural and Noisy Information
Many real-world applications require sorting in the presence of uncertainty or pre-existing structure. In the noisy comparison model, comparison outcomes may be unreliable. The independent noisy model assumes each comparison is flipped independently with probability p (0, 1), where p is the error probability. Recent work by Gu and Xu 2023) established optimal bounds for sorting elements under this model. In the recurrent noisy setting, proposed by |Braverman and Mossel 2007]. repeated queries between the same pair return consistent outcomes, Geissmann al. [2018] gave an optimal algorithm in this setting with On log n) time, Ollog n.) maximum dislocation, and ((n) total dislocation with high probability. These approaches generally focus on approximate sorting, and to the best of our knowledge, no prior work considers combining both clean (reliable) and dirty (unreliable) comparisons in exact sorting.
In parallel, adaptive sorting methods aim to exploit partial structure in the input to reduce computa- tional cost. Examples include TimSort [Peters] 2002] and Powersort [Munro and Wild 2018). These algorithms take advantage of presortedness, typically measured via global metrics like the number of inversions runs. Estivill-Castro and Wood [199]] provide comprehensive overview. While related in spirit, traditional adaptive sorting methods do not utilize explicit predictions or distinguish between comparison quality. Furthermore, their performance bounds are often based on aggregate error measures rather than element-wise guarantees.
1.2 Our Results
In this paper, we revisit median selection through two modern lenses that capture realistic constraints in learning and decision- making systems:
Median Selection with Strong and Weak Oracles. We formalize this setting using two com- parison oracles: a strong (accurate but expensive) oracle and a weak (cheap but noisy) oracle. Our modified LAZYSELECT algorithm strategically trades higher total number of oracle calls for a drastic reduction in costly strong queries. While the original LAZYSELECT requires ( strong comparisons in expectation, our method reduces this to ( strong comparisons, at the cost of O(n n) n. weak ones. This trade-off is highly advantageous in settings where strong queries are orders of magnitude more expensive.
Theorem 1 (Main Result 1). Let A be an array of elements and assume the weak comparison oracle errors independently with probability p < 1/2. Then, with high probability, the modified LazySelect algorithm returns the median of A using (1) O(n log running time, (2) O(n log weak comparisons, (3) Ö(r3/4) strong comparisons, (4) and succeeds with probability at least 1- O(n -1/4).
Structure-Aware Median Selection in Partially Ordered Sets. In structured domains, partial orderings among elements are often known priori, represented as directed acyclic graph (DAG). Such structure arises naturally in scheduling, causal inference, and preference modeling- We study median selection in this setting and design an efficient algorithm that exploits the DAG structure to minimize the number of necessary comparisons. Our approach prunes redundant queries and guides the search using order-theoretic insights.
Theorem 2 (Main Result 2). Let G = (V, E) be a DAG over n elements with width w, and let the Then the expected number of total comparison cost:
median element be selected using Algorithm
o ((11 (lggn + w log
11
logn)
w
3

---

In particular:
If O(1), the total number of comparisons is sublinear in n, specifically O(lgg" n). In the special case where the DAG is a single chain = 1), the recursion terminates after one step, and the median is found in (loo n) comparisons.
The compurison cost is o(n) whenever w log(n/w) o(n/ log n), oulperforming classical (n) methods for wide range of sparse DAGs.
Our results provide algorithmic techniques for median selection in realistic, structured, and Marning-augmenter environments. By leveraging side information-whetiee imate predictions partial orders-we demonstrate that substantial improvements baselines are possible. Our work contributes to the growing body of research at the intersection of algorithms, learning theory, and practical decision systems.
the form of approx- classical
Preliminary
2.1 Median Selection with Strong and Weak Oracles
We are given set S = 21, Z2..... In of n distinct elements, and the task is to identify the median element-i.e the element that ranks [n/2] / -th in the total order induced by their true values.
To perform comparisons, have access
types of oracles:
Strong Comparison Oracle (z b): Given any elements a, E S, this oracle returns the correct result of the comparison- -whthhrr a < b or > witt certainty. However, is expensive and should be used sparingly.
Weak Comparison Oracle with Persistent Errors (w, b): Given any two elements
a, b S, this oracle returns possibly noisy answer whether < b S be it returns the correct comparison outcome with probability 1-p > 1/2, and the incorrect one with probability p. Once the value of Ow (a, a, is fixed, it is used consistently throughout the execution (i.e., the error is persistent, resampling will not amplify the probability of correctness under this model).
The objective is to identify the true median of a set of elements using combination of strong and weak comparison oracles, such that:
Goal.
Correetness Guarantee: The algorithm returns the exact median element x² E S (i.e., the |n/2|-th smallest element in the true total order) with high probability, typically least 8, for some small >
2. Efficient Use of Oracles:
The expected number of queries to the strong oracle is sublinear in n e.g. o(n) or (n13/4 -n) reduce reliance on costly but accurate comparisons.
The number of queries to the weak oracle is also minimized, ideally remaining near- linear or better, while ensuring sufficient confidence to guide the use strong oracle queries.
The total running time should be Ö(n).
3. Robustness to Noise: The algorithm must tolerate uncertainty in the weak oracle (which returns correct outcomes with probability 1 p > 1/2) and strategically integrate both oracles to ensure reliable decision-man makiin..
2.2 Median Selection with Partial Order Prediction
Given a set n elements with an associated partial order represented as a directed acyelic graph (DAG) G (V, E), the objective is to identify the median element-thh that is, an element x E V such that at most [n/2] elements precede x= and at most [n/2] elements succeed x" in the true (but initially unknown) total order.

---

Formally, assuming the true total order < is consistent with the DAG G (up to potential noise), we seek element x" such that:
VueE:oraa S n 2
and V 1
n 2
The DAG G provides incomplete pairwise precedence information, which may derived from prior knowledge, historical comparisons, or predictive models. Our algorithm may query pairwise comparisons directly (e.g., via comparison oracle) resolve uncertainty. The goal is to exploit the DAG structure to (1) minimize the number of explicit comparisons required to find the median, and (2) avoid redundant comparisons by leveraging the transitive closure within the DAG.
The efficiency of our structure-aware algorithm depends on the width of the DAG, which is formally defined as the size of the largest antichain (a subset of vertices where no two are comparable under the partial order).
3 Median Selection with Strong and Weak Oracle
This section introduces LazySelect with Majority- Weak Oracle, a randomized algorithm for computing the median of an array using a combination of weak and strong comparison oracles.
3.1 Algorithm
We present robust adaptation of the LazySelect algorithm that operates with a weak comparison oracle, where each pairwise comparison returns incorrect result with probability p < To mitigate the effect of this noise, we compare each input element against a set of reference elements drawn from the sampled range boundaries and apply 2/3-majority rule over the aggregate outcomes. This ensures that the overall algorithm remains robust while preserving its asymptotic performance. The algorithm is detailed in Algorithm[]
The algorithm aims to efficiently compute the median of an array using unreliable (weak) comparisons, which may return incorrect results with some probability. To overcome this, first selects and sorts a small random sample from the input to estimate a central range [d, u| likely to contain the true median. Each input element is then compared against small set of reference elements near the boundaries of this range. Based on the majority of these weak comparisons, elements classified as likely smaller, larger, ambiguous. Only ambiguous elements are resolved using a reliable (strong) oracle. If this classification isolates a small set that must contain the median, the algorithm sorts this and directly extracts the median. Otherwise, it reports failure with low probability.
High-Level Idea:
The following steps detail how this idea is implemented in practice. Algorithm Description: The algorithm proceeds as follows:
1. Let = n///4, k = ni. Sample r elements uniformly at random from the input array A to form subset S, and sort S.
2. Define lower and upper bounds
S15 k:] and =S + k].
3. Let D be the largest clog elements in {x E S < d}. and U be the smallest clog elements in {a E S x 2 u).
4. For each A, compare each element of D U using weak comparisons and record the number of times the result < (denoted count and > (denoted county).
5. If count > 2/2 (count: count>), ), assign a E T.. If count> ? (count + county), assign R. Otherwise, use strong oracle to classify into L,, M, or R.
6. If classification succeeds with L < n/2 < |1 + [M], sort M and return the (n/2 - [ + 1h element of M as the median.
7. If the classification fails, report error.
5

---

Algorithm LazySelect with Majority-Vote Weak Oracle
Input: array A of size n
Output: Median element A
< n/ k + vn
Sample r elements from form S, and sort
I strong oracle
d < $ kl, u + 515 k
+ largest e clog elements Σ d, < smallest clog elements 2 u Initialize L, R. and M as empty
for each E do
counte, count, 4 for each E
U do
Compare a to d' and u' and update counte, county
D weak oracle
total <- count count> 10
11
if count > total then + {a}
12
else if count, > 2 total then R t {aa
13
else Compare a with d and u to decide whether to place a into I, M, or R. D strong oracle
14 if classification successful then
15
Sort M and return M L +
16 else
17
return
3.2
Analysis
This lemma formalizes the idea that the "middle" M remains small. Intuitively, since our pivots and u are chosen from a large random sample, the number of elements from the full array that truly fall between them is small, Furthermore, our majority-von scheme makes misclassification into M rare event, ensuring that the total size of M stays bounded.
Lemma 3 (Size of the Middle Region). With probability - On-nn((n)))))) 1/4),, the number of elements in the middle M (n3/4).
Here, we quantify the robustness of the majority vote. By performing O(log n) weak comparisons, we leverage concentration bounds (such as Hoeffding's 's inequality). Since the oracle better than random, the probability that the majority vote is incorrect decays exponentially, making misclassification polynomially unlikely in n.
Lemma 4 (Misclassification Probability). For element truly in L (respectively R), the probability of misclassification into M is O(n for some constant 7 = @(1), provided < 1/2.
This complexity bound follows directly from the previous lemmas. The costly strong oracle invoked only for elements that fall into the middle set M. Since Lemma guarantees that [M| ( with high probability, the cost of sorting this set remains sublinear.
Lemma 5 (Strong Comparison Complexity). With probability ((1))/)) the algorithm uses (n3344) strong oracle queries.
The proofs of Lemmas 3 5nd deferred to the Appendix.
We now summarize the full performance and correctness guarantees of the algorithm:
Theorem 6. Let A be array of n. elements, and suppose the weak comparison oracle returns an incorrect result independently with probability p 1. Then, with high probability, the modified LazySelect algorithm returns the median of A with the following guarantees: O(n log n) total running time, O(n log n)) weak comparisons, (113/1) strong comparisons, and success probability at least 1 1-
3.3 Generalization to the k-th Largest Element
Algorithm T extendd naturally to finding the k-th largest (or smallest) element by adjusting pivot selection and the success condition while preserving the core idea of using random sample to narrow

---

the search, Given a sample S of size r, pivots are chosen to bracket the expected rank of the k-th element, defined as
d = S
k r- ck
u s s
where cj ( (we choose Cg V as before) is a cushion parameter ensuring, with high probability, that the true k-th element lies in [d, u). The success condition becomes [L] < k S [M], where L and M are elements below d and between d, respectively; when satisfied, M sorted and M |4]]] returned. These modifications preserve sublinear strong comparisons and high success probability. enabling efficient retrieval of any k-th order statistic.
Remark, Achieving high-probubility median selection using only (n)) weak queries (with correct- ness probability p + <) and o(n) strong queries fundamentally challenging. This follows from two key barriers. First, the weak oracle limitation: prior work Braverman and Mossel (2007) shows that (n) weak queries misclassify each element with constant probability, producing (m) uncorrected errors. Second, the strong oracle sparsity: with only o(n) strong queries. most o(n) of these errors can be corrected. As result, (nn) - o(n) = (nn) errors remain, leading to median misidentification with probability - o(1). This highlights fundamental trade-off between query quality and quantity in median selection.
Median Selection with Structural Information
In this section, we develop median selection algorithm that exploits known partial order information represented by a directed acyclic graph (DAG). The key insight is that when partial order is available, many pairwise comparisons used in classical algorithms can be avoided. Our proposed algorithm leverages structure in the DAG to reduce the number of comparisons while still guaranteeing correctness. We present formal analysis establishing the correctness and efficiency of our method, and show how partitioning and refinement operations can be conducted efficiently using graph traversal and chain decomposition techniques.
4.1 Motivation and Overview
Let A = {ai,.... On } be set of n elements, and let G = (V,E) be a DAG over the elements in A, where (as, az) E E implies a; < aj- The DAG encodes partial information about the relative order of the elements. Our objective is find the true median of A, defined an element xx E A such that at most _ elements precede x² and at most elements succeed x² in the total order, using as few comparisons as possible.
The central idea is to use the DAG structure to predict the position of elements relative to a chosen pivot without performing explicit comparisons. We decompose the DAG into disjoint chains (by Dilworth's theorem), and refine partitions via binary search within each chain.
4.2 Algorithm Description
The algorithm performs median selection in partially ordered set represented as a DAG by recur- sively partitioning the graph around pivot. The Partition WithDAG procedure uses BFS and chain decomposition (via Dilworth's 's Theorem) to determine which elements are less than or greater than the pivot. The DediaanSelctiionUsing... subset depending on the size of the partition until it finds the median. The general procedure for partitioning using DAG structure is outlined in Algorithm while the randomized median selection using a DAG presented Algorithm 3 and the deterministic median selection using a DAG detailed in Algorithm 4 in the Appendix.
algorithm then recursively searches in the left or right
7

---

Algorithm 2 Partition with DAG Structure
Input: DAG G (V, E., pivot element q Sets L and R. where L = { E x R {x V
Output:
x > 5}
Initialize T. <- 0, R <- 0
Perform BFS from q the reverse direction to find all with path x - qi add to 7.
Perform BFS from Decompose G into chains Ci...., Cr using Dilworth's Theorem
the forward direction to find all with path q a. add to R
for each chain C; do if E C then Use binary search in C to classify remaining elements relative
else
Use binary search in C2 to determine if any elements comparable to q
10
Add elements smaller/larger than to L/R accordingly
11 return L, R
Algorithm 3 Randomized Median Selection Algorithm Using DAG
Input: DAG G E), where is set of n elements Output: Median element of V
if n m==1 then
return the single element
Select pivot q E V (randomly or deterministically) R PARITIONWITIDAAIGG..
if [L] [n/2] then
return 9
else if | [n/2] then
G' +- induced subgraph of on I,
return NEDIANSST.CCTIONSSSNNID.C
10
else
11
induced subgraph of G on R
12
- 1n/ -1|-1
13
return MEDINNSELLCTIIONSNNNAAAACCCC with adjusted rank k'
4.3
Theoretical Framework
We now formalize the key properties and theoretical foundations of the algorithm.
While seemingly definitional, this lemma is crucial confirms that simple graph traversal (BFS)
correctly identifies a subset of relationships via transitivity without requiring any new comparisons.
Lemma 7 (Correctness of BFS Classification). Let G = =V,E) be DAG over set of elements A.
and let q E A be pivot element. Define:
Lg {o E A there exists a path from æ to g)
Rg = A) there exists a path from q to x}
Then for all x E Lgg we have g, and for all x E Rag we have > q.
This classic theorem serves as the cornerstone of our algorithm. It allows us to decompose any complex partial order into small number (w) of simple, totally ordered chains.
Lemma 8 (Chain Decomposition via Dilworth's Theorem Dilworth [1987]) Let == = be DAG with width Then, the veriex set V be partitioned into most disjoint chains C1, C2,..., Ou, where each Cs is a totally ordered subset V.
Lemma (Correctness of DAG-based Partition). Given a pivot q, and chain decomposition (Ct,...,Cul) let each chain C₁ be ordered, and let ig be the index of q in its chain C.. Then all elements preceding in C; are less than q, and all elements following q greater than assuming consistency of partial order.

---

4.4
Complexity Analysis
Let n be the number of elements and w the width of the DAG. The graph traversal, including BFS and inverse BFS, takes (n) time. Chain decomposition, using known algorithms Cáceres [003)] requires (n log time. Binary search of chains has total number of comparison of O(w (og(n/vu) n/))) (The reason is given in the proof of Theorem 10). Therefore, the overall number of comparisons significantly less than (n)) when w < n, which is typical structured or low-width datasets.
E) be a DAG over n elements with width w, and let the median element be selected using Algorithm 3 Then the expected number of comparisons required O (log w log (w) per recursive step, resulting in total comparison cost ((log n + w log (w) logn).
Theorem 10 (Comparison Complexity with Structural Information). Let G = EV.E)
Moreover, the algorithm adapls naturally to structured domains such as tournament graphs, hierar- chical workflows, or ranking-busse posets, where the width w is typically small.
The proofs of Lemmas
and Theorem 10 are deferred to the Appendix.
This hybrid approach offers an efficient and principled strategy for median selection in the presence of both noisy comparisons and structured side information. By combining chain decomposition, transitive pruning. and robust refinement, the algorithm achieves correctness while minimizing explicit comparisons eeppecial in settings with inherent partial order structure.
5 Experiments
We empirically evaluate our algorithms two settings: (1) the classical total order case, where weak comparison oracle is available, and (2) the partially ordered case, where the input is a synthetic DAG and only standard comparisons are used. the first setting, our goal is to compute the exact median while minimizing costly strong comparison calls. In the second, we aim to reduce the total number of comparisons by leveraging the partial order structure. All experiments use synthetic data: we vary the weak oracle accuracy in the total-order case and control the DAG width in the partial-order case.
5.1 LazySelect with Majority Vote
We begin by evaluating our modified LazySelect algorithm on arrays of size n = 10 and n = 10% each random permutation of (0, (O..... normalized number of strong oracle calls per element across weak oracle accuracies (0.51, 0.75, 0.9, 1.0) and weak comparison budgets e d, where d log and 41,2,4,8, 16). Each configuration is repeated 100 times, and we report average results.
1}. We report the exact median success rate and the
p E
gronn Oracio Calls, F
Serona Oracie Calls
Success Rate
Success Rate
8.
60
Weak Oracle Calls (c d)
Weak Dracle Callstc-o)
Weak Oracle Calls (c d)
25
Weak Oracle Calls(c-d)
28
(a)
10
(b) m 10
Figure 1: Success rate and the number of strong oracle calls normalized by the array size n, with respect to the weak comparison budget e d. Each color represents a different weak oracle accuracy.
over 94% accuracy when 10 Figure I shows that in the noisiest case (1 --pp p = 0.51), only when e 2 8 does the success rate exceed 95%, yet the number of strong comparisons remains nearly that, under very noisy
identical to the average from 100 runs of standard LazySelect-indiene conditions, additional weak votes provide negligible benefit. For p 0.75, the success rate exceeds 97% at = 4 and reaches 100% by e = Finally, for high-quality oracles (1 - p 2 0.9), only 2 log n weak comparisons suffice to achieve over 94% accuracy. In all cases except when 1 1-p p- = 0.51, the number of strong oracle calls lower than that of standard LazySelect. Similar trends are observed for both 1 and 106

---

5.2 Directed Acyelic Graph Setting
We next evaluate the impact of structural information by comparing both the randomized (Algorithm 3 and deterministic (Algorithm 9 median selection algorithms, with and without access to DAG structure. on synthetic partial orders over 10* elements. DAGs are generated by randomly adding edges while preserving acyclicity, and we control the width w (size of the largest antichain) by varying edge density in steps of 500. Results are averaged over 10 trials per width.
#Comparisons /
# #Comparisons
WDAG
width(DAG)
domioed
Portition Sorting Compartsons
Deterministic
Figure 2: Number of comparisons normalized by the array size тı, with respect to DAG width w. Left: random pivot; Right: median-of-median, pivot. The solid line indicates the performance of the classical median-of-median algorithm (which ignores the DAG structure), serving as our baseline. Shaded areas show one standard deviation over 1,000 runs for the bascline.
Figure shows that for large widths (w 10,000), both pivot strategies incur approximately 5-6 comparisons (normalized by n). As w decreases to around 2, 000, the randomized and deterministic strategies require approximately 3.0 and 4.5 comparisons, respectively. When w & 500, these values drop to about 1.7 and 2.9. At w = 1, both strategies require nearly zero comparisons. The deterministic strategy yields smoother curve, while the randomized exhibits more variance but follows similar downward trend.
Limitations of Synthetic Data. Our experiments are conducted on synthetic datasets enable controlled evaluations where parameters such noise levels and DAG width can systematically varied, allowing to validate our theoretical findings. Evaluating our algorithms on empirical datasets remains an important direction for future work.
Conclusion
In this paper, we presented a selection under two distinct yet practically motivated settings. In the first, we explored how to effectively combine weak and strong comparison oracles to identify the median while minimizing the number of expensive strong comparisons. Our algorithm achieves sublinear strong query complexity in expectation, making it well-suited for settings where comparison costs vary significantly. In the second setting, we leveraged partial order information encoded in a DAG to reduce the overall number of comparisons needed for median selection.
approach to the classical problem of median
To validate our theoretical contributions, we conducted series of experiments evaluating both the oracle-based and DAG-based algorithms. The results consistently show that our proposed methods outperform standard baselines in terms of comparison efficiency and accuracy.
Acknowledgments
We thank the anonymous NeurlPS reviewers for their insightful feedback. This work was supported by the New Faculty Startup Fund and conducted with the Algorithmic Foundations Data Science Lab at Scoul National University.
10

---

References
Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In International Conference Machine Learning, pages 582-598. PMLR, 2022.
Spyros Angelopoulos, Christoph Düm, Shendan Jin, Shahin Kamali, and Mare Renault. Online computation with untrusted advice. Journal of Computer and System Sciences, 144: 103545, 2024.
Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Mixing predictions for online metric algorithms. In International Conference on Machine Learning, pages 969-983. PMLR, 2023.
Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1070-1080, 2021.
Xingjian Bai and Christian Coester. Sorting with predictions. Advances in Neural Information Processing Systems, 36:26563-288 -65544, 2023.
Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. weighted paging. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA), pages 67-89, SIAM, 2022.
Ziyad Benomar and Christian Coester. Searning-augmente priority queues. arXiv preprint arXiv:2406.04777 2024.
Avrim Blum and Vaidehi Srinivas. Competitive strategies to use "warm start" algorithms with predictions. Proceedings of the 2025 Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3775-3801 SIAM, 2025.
Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, Robert Endre Tarjan, et al. Time bounds for selection. J. Comput. Syst. Sci., 7(4):448-461, 1973.
Jan van den Brand, Sebastian Forster, Yasamin Nazari, and Adam Polak. On dynamic graph algorithms with predictions. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3534-3557. SIAM, 2024.
Mark Braverman and Elchanan Mossel. Noisy sorting without resampling. arXiv preprint arXiv:0707. 1051, 1051, 2007.
Manuel Cáceres. Minimum chain cover almost linear time, arXiv preprint arXiv:2305.02 2023.
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
Constantinos Daskalakis, Richard M Karp, Elchanan Mossel, Samantha Riesenfeld, and Elad Verbin. Sorting and selection in posets. SIAM Journal Computing, 40(3):597-622, 2011.
Robert P Dilworth. A decomposition theorem for partially ordered sets. Classic papers in combina- forics, pages 139-144, 1987.
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. Advances in Neural information processing systems, 34: 10393-10666. 2021.
Michael Dinitz, Sungjin Im, Thomas Lavastida, Ben Moseley, Aidin Niaparast, and Sergei Vassilvit- skii. Binary search with distributional predictions. Advances Neural Information Processing Systems, 37:90456-990 90472, 2024.
Jon C Ergun, Zhili Feng, Sandeep Silwal, David P Woodruff, and Samson Zhou. Learning-auggentee k-means clustering. arXiv preprint arXiv:21 / 10. /4094, 2021.
Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Sorting and hypergraph orientation under uncertainty with predictions. arXiv preprint arXiv:2305.09244 2023.
11

---

Vladmir Estivill-Caase Castro and Derick Wood. A survey of adaptive sorting algorithms. ACM Computing Surveys (CSUR), 24(4):441-476, 1992.
Robert W Floyd and Ronald L Rivest. Algorithm 489: The algorithm select-for finding the th smallest of elements [ml]. Communicutions of the ACM, 18(3):173, 1975.
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal sorting with persistent comparison errors. arXiv preprint arXiv: 1804 005.07575, 2018.
Yuzhou Gu and Yinzhan Xu. Optimal bounds for noisy sorting. In Proceedings the ACM Symposium on Theory of Computing, pages 1502-1515, 2023.
the 55th Annual
Charles AR Hoare. Algorithm 65: find. Communications of the ACM, 4(7):321-322 1961.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and trends@ in machine learning, 14(1-2):1-210, 2021.
David Karger, Sewoong Oh, and Devavrat Shah. Iterative learning for reliable crowdsoureing systems. Advances in neural information processing systems, 24, 2011.
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 international conference on management of data, pages 489-504, 2018.
Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In Interna- fional Conference on Machine Learning, pages 13431-13440. PMLR, 2022.
Alexander Lindermayr and Nicole Megow. Permutation predictions non-clairvoyant scheduling. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, pages 357-368, 2022.
Pinyan Lu, Xuandi Ren, Enze Sun, and Yubo Zhang. Generalized sorting with predictions. In Symposium Simplicity in Algorithms (SOSA), pages 111-117. SIAM, 2021.
Tyler Lu and Craig Boutilier. Learning mallows models with pairwise preferences. In Proceedings of the 28th international conference on machine learning (icml-11), pages 145-152, 2011.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1-25, 2021.
Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
J Ian Munro and Sebastian Wild. Nearly-optimal mergesorts: Fast, practical sorting methods that 2018.
optimally adapt to existing runs. arXiv preprint
Tim Peters. Re: Timsort python-dev mailing list. Python-dev Mailing List Post, July 2002. URLhttps:: //mail, python. orgpppemmallyyyttooeorr///oonoor cessed: May 8, 2025.
httml Ac-
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018.
Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium Discrete Algorithms, pages 1834-1845 SIAM, 2020.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract and introduction summarize the main contributions and their
scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We mentioned that our results hold on with high probability in the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

All theoretical results are stated with full assumptions and complete proofs, provided in the main body of paper and Appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The paper provides all necessary details to reproduce the results, including parameter settings and evaluation procedures.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Provided in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //iips.cc/pplll wttpcccpppppppppeeeeeeeeeeeeeeee httpa///giiieee/eeeeebiiisssssss /Cc////oddiiisssseeeeeee www.iissssiiiiiiiico for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
All relevant settings and parameters are specified the experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The LazySelect experiments are repeated 100 times per setting, and the DaGebased experiments are repeated 10 times. We report average results in both cases.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We stated the computer resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We follow the code ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is mainly theoretical and focuses on algorithmic analysis; it does not involve applications with direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We present theory work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: All data and code used in this work developed by the authors; external assets were used.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve human subjects or crowdsourcing in any form.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This work does involve human subjects and does not require IRB approval.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This research does not involve LLMs any core method, experiment, or result.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hbtp:e///harripeccc//o/ofrrrrr// for what should or should not be described.
19

---

A Algorithm Deferred from Main Text
Algorithm 4 Deterministic Median Selection Using DAG (Median of Medians)
Input: DAG G (V, E), where is set of elements
Output: Median element of V if' = then
return the single element
Divide V into groups of at most 5 elements each for each group do
Compute the median of the group using DAG comparisons
Let M be the set of medians from all groups
Construct DAG G induced on M
<
Recursive call
9 L, R <- PARTITIONWITHIAG((....) m)
10 if [Z] [nn/2] then
11
return m
12
else if L| [n/2] then
13
G" t induced subgraph of G on L
14
return MEDIANSILCCTONUSSGGAAGCI
15
else
16
G <- induced subgraph of on R
17
/ |n/2] [L| -
return MEDIANSELLCCTOONUNNNAAAGCC with adjusted rank k' 18
B
Proof Deferred from Main Text
B.1 Proof for Lemma
Proof. 1. Original Middle Region Moriginal:
The algorithm samples 3/3 elements uniformly from A, sorts them form S, and selects pivots d and u such that:
d d= d= -=
u == k where k Vn.
The interval [d, u) in S contains 2 = 2/n elements. By the Chernoff bound, the number of elements in A between and concentrates around 0/43/4) with probability 1 1 10O(n-10 1/4) (see Mitzenmacher and Upfal 2017)).
Thus, |Moriginal| = ((23/4) with probability 1 (1141)).
2. Misclassification into M:
Let Mmis denote elements misclassified into M due weak comparison errors.
For element L (truly I d), the probability of misclassification is the probability that fewer than
2c log n weak comparisons return <.
Let X be the number of correct < comparisons. Each comparison succeeds with probability p, so:
E 2c (1 p).
Using Hoeffding's 's inequality for <
4e
logn:
3
4c
(2clog (1 p)
4e log n)
X
<
log n
< exp
3
2clog n
20

---

Simplifying the exponent for < 1/2:
P(mmisclasifiiatioo)) S (exp(-2(logn)) n)) O(n 7)
where = (1))
3. Bounding |Mmisl:
The expected number of misclassified elements is:
E||lMmis|] S O0 = 0
By Markov's inequality:
P (IMmisl 2 n n²/4)
E1 Mmill O( Onn On
3//11
provided y 2 1/4.
Total Size of M:
Combining both components:
M = |MMrrinnnal + Mmiis = 0(n3/4) + 0(n3/4) = Onn214)
with probability On
B.2
Proof for Lemma
Proof. Let X be the number of correct weak comparisons for an element E L. Each weak comparison succeeds independently with probability 1 p. so the expected number of correct outcomes is
[ = 2clog n (1-p).
For misclassification into the middle region M, the number of correct votes must fall below the threshold, i.e., X log Applying Hoeffding's inequality for bounded independent variables:
4c
P
x
log
S exp (- m)) O(n ?),
for constant 7 > 0 that depends and Summing over all n elements, the expected number of misclassified elements is
BiJJmiss]] = n nnnnnn = O(n' (7)
Applying Markov's inequality, we have
IP (IMmisl > 0(13/4) (nn-1/1)
for suitably chosen constant 7 > 1/4. Hence, with high probability, the number of misclassified elements in M is bounded by (n3//))
B.3 Proof for Lemma
Proof. By Lemma only ((n3/4) elements fall into the uncertain middle region M, each requiring constant number of strong comparisons. The number of exact comparison in sorting is On logn) Hence, the total number of strong comparisons is Ö(n3/44 with high probability.
B.4 Proof for Lemmal 7
Proof. By definition of reachability in DAG, there path ..... q, then transitivity the partial order implies q. Similarly, if q + + then g
D
21

---

B.5 Proof for Lemma 8
This direct application of Dilworth's Theorem, which states that the minimum number of chains needed to cover partially ordered set equals the size of its largest antichain. Since the DAG has width w, the size of its largest antichain w, so the vertex can be decomposed into w chains.
Proof.
B.6 Proof for Lemma
Proof. Within each chain C, the elements totally ordered. Hence, binary search can be used find the relative position of g, and the local order within each chain ensures the correctness of the partition around q. This partitioning respects the partial order and contributes to the global ordering of A.
C Proof of Theorem 10
To determine the relationship between the pivot q and each element v E V (g), we exploit the structure of the DAG. By Dilworth's Theorem, DAG of width w can be partitioned into w chains C1. Ct.Co...., Cw. where each chain is totally ordered.
Let n, denote the number of elements in chain C,, so that Σ n. = n. Since elements within chain are totally ordered, we can determine the relationship between g and any element C2 using binary search within that chain, which takes Oloog n.) comparisons.
Therefore, the total number of comparisons needed to partition all elements with respect to g is:
Olog ns).
Applying Jensen's inequality (or noting that the logarithm is concave), we get the bound:
w
log n. S w log
T4
log
W
Thus, the partitioning step takes
(w log(n/w))
comparisons in total.
Including an additional Ollog n) factor for selecting the pivot and bookkeeping, the total expected number of comparisons per recursive step becomes:
O log n + w log
w
D Experiments Setup
Experiments were conducted on MacBook Air (M1, 2020) with GB RAM. All code was compiled under the C++17 standard with the -03 optimization flag. Since our algorithm relies on lightweight comparison operations rather than heavy machine learning training, performance is not significantly affected by hardware. All source code used for these experiments is provided in the supplementary material as a ZIP archive.
22


Reviews:
[{"review_id": "RTXCiT7HbF", "reviewer": "Reviewer_JGL7", "summary": "The paper studies exact median selection under two settings: (1) noisy comparisons\n from both weak (inexpensive, error-prone) and strong (accurate, costly)\noracles, and (2) inputs with partial order represented as DAGs. \n\nFor the first setting, the authors propose a modiffed LazySelect algorithm that uses majority\n voting among weak comparisons to reduce the number of strong oracle calls,\nachieving sublinear strong comparison complexity with high-probability correctness.\n\nFor the second setting, the authors exploit structural information in the\nDAG to design a median selection algorithm that requires signiffcantly fewer\ncomparisons when the DAG has small width. \n\nBoth algorithms are analyzed theoretically and supported by experiments on synthetic data.", "questions": "1. Can a similar method be used to ffnd the kth largest number instead of\nthe median?\n\n2. Is it possible to keep the weak oracle query at O(n) in Theorem 1?", "limitations": "The algorithm for solving noisy comparison will call weak oracle O(n log n)\ntimes. The algorithm for solving DAG improves only when the width is small,\nand performs worse than the classic algorithm when the width is close to n.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. The paper effectively integrates weak and strong comparisons, achieving\nsublinear use of the expensive strong oracle.\n2. By leveraging partial order (DAG) structure, the proposed algorithm signiffcantly\n reduces comparison complexity when the DAG has small width.\n3. The experiments validate both algorithms under varied noise levels and\nDAG structures, conffrming the theory.\n\nWeaknesses\n1. Theorem 1 shows that the total number of oracle calls of the proposed\nalgorithm is O(n log n), which is larger compared to the O(n) of median\nof median algorithm or lazy selection algorithm mentioned in the paper.\nSince the probability of a weak oracle being correct is greater than 1/2,\nit is not a very nontrivial result to be able to use log n times of the weak\noracle instead of once the strong oracle.\n2. While Algorithm 1 presents an interesting modiffcation of the LazySelect\napproach, the paper would benefft from a more explicit comparison with\nthe original LazySelect algorithm.\n3. According to the conclusion of Theorem 2 recounted at line 131, the corollary\n after line 132 is incorrect, with one less log n term taken into account.", "was_revised": true, "final_justification": "The authors have clarified most of my questions and concerns, including (1) the clarification of the algorithm's generalizability to finding the k-th largest element, (2) the explanation of the theoretical impossibility of reducing weak oracle queries, and (3) the clarification of this work's main contribution. Overall, the theoretical analysis of the paper is solid. However, the core approach that using majority voting to replace one strong query with O(log n) weak queries is somewhat straightforward, hence my final rating of borderline accept.", "rebuttal": "**Dear Reviewer JGL7,**\n\nThank you for your valuable time and constructive feedback on our work. We appreciate that you found our integration of weak/strong oracles and the use of DAG structures effective. Below, we address your specific concerns in detail.\n\n\n **Addressing Questions**\n\n#### **1. Generalization to k-th Largest Element**\n\nYes, Algorithm 1 can be generalized to compute the *k*-th largest element, not just the median. The core idea—using a sample to identify pivot elements that isolate the target in a smaller subproblem—remains unchanged. The required modifications are as follows:\n\n##### 1.1 Adjusting the Pivot Selection\n\nThe original algorithm selects pivots $d$ and $u$ to form a confidence interval around the median’s expected rank. To generalize this to the *k*-th element, we center the interval around the expected rank of the *k*-th element in the random sample $S$ of size $r$, which is $r \\cdot (k/n)$.\n\n**Modification:** The bounds $d$ and $u$ are redefined as:\n\n$$\nd = S\\left[\\left\\lfloor r \\cdot \\left(\\frac{k}{n}\\right) - c_k \\right\\rfloor\\right], \\quad\nu = S\\left[\\left\\lceil r \\cdot \\left(\\frac{k}{n}\\right) + c_k \\right\\rceil\\right]\n$$\n\nThis adjustment ensures that the selected range accurately captures the desired rank interval around the $\\frac{k}{n}$-quantile, scaled by the sample size $r$ and buffered by $c_k$.\n\nHere, $c_k$ is a cushion parameter (analogous to the original setting $c_k = \\sqrt{n}$) that guarantees the true *k*-th element lies between $d$ and $u$ with high probability.\n\n##### 1.2 Updating the Success Condition and Final Selection\n\nThe original condition for the median, $|L| < n/2 < |L| + |M|$, must be updated for the *k*-th rank.\n\n**Modification:** The new success condition becomes:\n\n$$\n|L| < k \\leq |L| + |M|\n$$\n\nThis ensures that exactly $k$ elements lie in the union of $L$ (less than target) and $M$ (equal to or around the target).\n\n**Modification:** Once this condition is satisfied, the algorithm sorts the set $M$ and returns the element at position $k - |L|$ in the sorted list.\n\nWith these updates, Algorithm 1 generalizes to compute any order statistic. Theoretical guarantees, such as achieving sublinear strong oracle complexity with high probability, still hold under this modification.\n\n\n\nFor the DAG algorithm (Algorithm 3), the recursive step can search for an element of rank $k$ instead of the median ($n/2$). The algorithm already supports $k$-th element selection, and this functionality is implemented in the supplementary document submitted.\n\n\n\n\n#### **2. Reducing Weak Oracle Queries to $O(n)$**\n\nWe agree this is a fundamental challenge. In fact, we can formally argue that no algorithm can achieve high-probability median selection with only\n$O(n)$ *weak queries* (with correctness probability $p = \\frac{1}{2} + \\epsilon$) and\n$o(n)$ *strong queries*, due to two core limitations:\n\n* **Weak Oracle Limitation:**\n  Previous work showed that using only $O(n)$ weak queries leaves each element misclassified with constant probability, leading to $\\Theta(n)$ uncorrected errors.\n\n* **Strong Oracle Sparsity:**\n  With only $o(n)$ strong queries, we can correct at most $o(n)$ errors. Thus:\n\n  $$\n  \\Theta(n) - o(n) = \\Theta(n)\n  $$\n\n  errors remain uncorrected, causing median misidentification with probability $1 - o(1)$.\n\nThe $O(n \\log n)$ weak query complexity in our algorithm arises from the majority-vote subroutine, which requires $O(\\log n)$ weak comparisons per element to amplify correctness. However, when the oracle’s error rate is sufficiently low (e.g., $p = 1/2 + \\Omega(1/\\log n)$), the number of required weak comparisons per element can drop to $O(1)$. We will explore and clarify this trade-off in the revised version.\n\n\n **Addressing Weaknesses**\n\n#### **Weakness #2: Comparison with Original LazySelect**\n\nWe agree that a direct comparison with the original LazySelect will enhance the paper. In the classical LazySelect, all comparisons are strong and error-free, with total query complexity $O(n)$. Our variant replaces most strong comparisons with $O(\\log n)$ weak comparisons per element (via majority voting), while reducing strong queries to $\\tilde{O}(n^{3/4})$. Though total oracle calls rise to $O(n \\log n)$, this is a favorable trade-off given the high cost of strong queries. We will add a comparison table to highlight this trade-off in the revised manuscript.\n\n#### **Weakness #3: Theorem 2 Corollary**\n\nThank you for pointing out the imprecise phrasing.\nThe correct bound for $w = O(1)$ is indeed $O(\\log^2 n)$, as can be seen from Theorem 2, which gives a bound of\n$O\\big((\\log n + w \\cdot \\log(n/w)) \\cdot \\log n\\big).$\nHowever, when the DAG width is exactly 1, there is only a single chain and the recursion depth becomes 1. In this case, we can find the exact median using only $O(\\log n)$ comparisons.\nWe will revise the corollary accordingly. The main theorem remains correct as stated.\n\n\n#### **Weakness #1: Nontriviality of Sublinear Strong Queries**\n\nWhile the weak oracle is more powerful than random guessing, our key contribution lies in the hybrid design: leveraging weak queries while preserving sublinear use of expensive strong queries (i.e., $\\tilde{O}(n^{3/4})$). Prior works typically assume either all-clean or all-noisy settings. Our result bridges these extremes. We will clarify this point in the revision to better highlight its novelty.\n\n\n **Addressing Limitations**\n\n#### **Noisy Comparison Algorithm’s Weak Query Usage**\n\nThe use of $O(n \\log n)$ weak queries is necessary for robustness via majority voting. While this exceeds the complexity of noiseless algorithms, it is a necessary overhead for dealing with unreliable comparisons. In future revisions, we will discuss possible improvements, such as adaptive voting strategies that reduce overhead when the oracle’s bias is large.\n\n#### **DAG Algorithm’s Dependence on Width**\n\nAs noted, the performance of our DAG-based algorithm depends critically on the width $w$. This is unavoidable: when $w = \\Theta(n)$ (e.g., in a complete DAG), no structural advantage exists and $\\Omega(n)$ comparisons are needed. We will emphasize this structural trade-off more clearly in the final version.\n\nThank you again for your detailed and highly valuable feedback."}, {"review_id": "keW2qcoAhA", "reviewer": "Reviewer_NEam", "summary": "This paper studies the problem of finding a median from 1) a complete order using noisy pairwise comparison queries and 2) a partial order using non-noisy queries.\n\nFor the first problem, they are given an order over n elements. They are allowed to make two types of queries over pairs of points: 1) a strong query, which always returns the correct order between the points, and 2) a weak query, which outputs an incorrect order with probability < 0.5. A good solution should use sublinear strong queries, and at most linear (preferably sublinear) weak queries. This model is based off a handful of previous works in related areas. The problem has not been studied with respect to strong and weak queries together, but it has been studied with respect to strong queries only.\n\nTheir solution is an adaptation of Rivest and Floyd's lazy select algorithm, which is loosely modeled after quicksort. What they do is they sample a large (but sublinear) set of points as a sort of \"pivot set\" akin to the quicksort algorithm. With high probability, the middle 2sqrt(n) of sampled points encapsulates the median. They take points along the edge of this middle range and use them to sort the rest of the points as low, high, or in the middle range. When they sort a single point, they compare them to all sampled points in this range, and if sufficiently many state it is low or high, then it is sorted as such. If there is not a strong enough majority, then strong comparisons are used to definitively order the points. After sorting, the middle range is ordered and they can identify the median from the middle range with high probbaility.\n\nFor the partially ordered problem, they use existing methods to decompose the DAG representing the order into a number of disjoint chains, and then they can use binary search methods along these chains to implement a sort of quicksort algorithm. Note that this problem is generally easier than the other problem, since a median is only defined by having sufficiently few smaller or larger nodes than this (and so having more unorder in the partial order means more points could constitute a valid median).\n\nExperiments are run on synthetic datasets. For the completely ordered problem, random permutations are used. They find that using logarithmically many weak oracle calls, they can achieve near perfect success rate in practice, but if the probability of an incorrect label is too high, the number of strong oracle calls is also high. For the partially ordered problem, DAG are generated by random edge generation, and they see that the number of comparisons decrease as the DAG width decreases.", "questions": "1. In Theorem 2, it doesn't seem like the \"in particular\" part follows. The general total comparisons you have can be rewritten as O(log^2n + w log(n/w) log(n)). Therefore, no matter what w is, it can't be below O(log^2 n). Additionally, if w = n / log(n) = o(n), the latter term becomes O(n loglog(n)), which is not o(n) as stated. Perhaps these are additional results you found that aren't important special cases of the general formula you have above? If so please clarify that, because it's confusing as written.\n\n2. If the error of the weak oracle were not fixed, would you even be able to leverage resampling to obtain a better algorithm? As in, is this assumption necessary to make your results interesting?\n\n3. Do you think your work has any notable relation to rank aggregation? In this problem, you're given a number of permutations over [n] and are asked to output a sort of \"median ranking\" over the set. Quicksort has a nice analog here, where you create your ordering using pivots and then taking a majority vote over the permutations asking if each value is higher or lower than the pivot. The majority vote is nontransitive, meaning there is uncertainty of what order would result dependent on the order of pivot selection. This is obviously distinctly different from the noise you're considering, but it's reminiscent of it, and I'm wondering if some techniques are transferable between the problems. (This is also similar to the DAG formulation, but here we may have cycles). \n\n4. In Section 3.1, the algorithm description, step 5, what are you comparing a to for the strong oracle? Also you did not adequately describe what criteria puts a into M.\n\n5. For the DAG problem, you discuss \"the true median\" on line 243. Aren't there potentially many possible medians that satisfy this for a DAG? I mean, theoretically every point could be a median. The way you word it here seems to imply it's unique.\n\n6. Are Lemmas 7 and 9 not just restating the definition of the order imposed by the DAG?\n\n7. Please include a brief definition of DAG width.\n\n8. What do you mean by \"the algorithm adapts naturally to structured domains such as...\"?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The median selection problem is a fundamental problem so any work on this problem is interesting. The noisy model they use has been used before and makes some intuitive sense, though I would really like to see more evidence that it is a useful model to look at. Their results for both problems are sensible and imply nice, straightforward algorithms. The methods are somewhat interesting extensions of existing algorithms.\n\nThe writing is easy to follow but they admit most of the intuition as to why their methods work. Their analysis sections in 3.2, 4.3, and 4.4 are basically lists of lemmas which I find nearly unacceptable. The experiments are nice to have and portray interesting trends, but I would say their interest is limited partly by how little experimental analysis was done but also because the synthetic dataset generation is extremely basic and not likely to resemble real world distributions.", "was_revised": true, "final_justification": "This work is solid but I do not think the writeup is ideal quality for an accepted paper.", "rebuttal": "**Dear Reviewer NEam,**\n\nThank you for your thorough and thoughtful review. We appreciate your positive remarks on the importance of the problem and the clarity of our algorithmic contributions. Below, we address your concerns and questions point by point.\n\n\n\n 1. **On the Presentation of the Analysis**\n\nWe agree that presenting the analysis as a \"list of lemmas\" without sufficient intuition is not ideal. While the complete formal proofs are provided in the appendix, we will revise the main text to include high-level proof sketches and intuitive explanations for each lemma to improve readability and motivation.\n\n\n\n2. **On the Synthetic Nature of Experiments**\n\nWe acknowledge that our experiments are based on synthetic data. This was an intentional design choice to create a controlled setting where we can precisely vary key parameters such as noise levels and DAG widths to empirically validate our theoretical results. We will add a discussion in the limitations section to acknowledge that real-world data may introduce additional complexity and that evaluating the algorithm on such datasets is an important direction for future work.\n\n\n 3. **Responses to Specific Questions**\n\n* **Theorem 2 Complexity:**\n  Thank you for catching this. \nThe correct bound for $w = O(1)$ is indeed $O(\\log^2 n)$, as can be seen from Theorem 2, which gives a bound of\n$O\\big((\\log n + w \\cdot \\log(n/w)) \\cdot \\log n\\big).$\nHowever, when the DAG width is exactly 1, there is only a single chain and the recursion depth becomes 1. In this case, we can find the exact median using only $O(\\log n)$ comparisons.\nWe will revise the corollary accordingly. The main theorem remains correct as stated.\n\n* **Persistent Weak Oracle Error:**\n  The assumption of persistent noise is standard in the literature and essential to the non-triviality of the model. Without persistence, one could simply resample the same pair $O(\\log n)$ times to reduce error probability to $1/\\text{poly}(n)$, rendering the weak oracle nearly as powerful as a strong one. The persistent model captures systematic noise, such as a biased annotator. We will add this clarification to the revised version.\n\n* **Relation to Rank Aggregation:**\n  This is an excellent observation. The main distinction lies in the assumption of an underlying total order in our setting, which ensures transitivity—unlike in rank aggregation problems, where preference cycles (e.g., Condorcet paradoxes) may occur. That said, both models aim to infer global rankings from noisy input, and we will add a brief note in the related work section to highlight this connection.\n\n* **Algorithm 1, Step 5 (Use of Strong Oracle):**\n  We apologize for the ambiguity. In Step 5, the strong oracle is used to compare an element $a$ against the pivots $d$ and $u$, determining definitively whether $a < d$, $d \\leq a \\leq u$, or $a > u$. An element is placed in the middle set $M$ if it cannot be confidently placed in $L$ or $R$ using the weak oracle or if it is explicitly placed there by the strong oracle. We will revise the description of Algorithm 1 to make this process more explicit.\n\n* **\"True Median\" Terminology:**\n  You're right—the phrase “the true median” is misleading in the context of a DAG. What we mean is the median with respect to some total order consistent with the DAG. We will revise this phrasing to “a median of a consistent total order” to ensure precision.\n\n* **Lemmas 7 and 9:**\n  While these lemmas may appear definitional, they are essential steps in our correctness analysis. They formally verify that our BFS traversal and chain-based partitioning procedures correctly leverage the transitive structure of the DAG to classify elements without error.\n\n* **Definition of DAG Width:**\n  We will add a formal definition of DAG width (i.e., the size of the largest antichain) in the preliminaries to eliminate ambiguity.\n\n* **\"Adapts naturally to structured domains...\":**\n  We agree that this statement can be more concrete. We will revise it to:\n  *“The algorithm’s performance, as shown in Theorem 2, improves as the width $w$ of the DAG—representing its structural complexity—decreases.”*\n\n\nThank you again for your detailed and highly valuable feedback."}, {"review_id": "SColoHkjTD", "reviewer": "Reviewer_2hww", "summary": "This paper studies the median selection problem with noisy comparisons results. In this paper's setting, each pair of items can only be queried once (further queries will give the same results). When querying a strong oracle, the correct relations of them will be returned. When querying a weak oracle, the correct relation will be returned with probability 1-p>1/2. This paper further studies the case with a prior known comparison relations (represented by a DAG).\n\nFor the first case, this paper proposes an algorithm that needs O(n\\logn) weak oracle queries and \\tilde{O(n^0.75)} queries of the strong oracle, and returns the correct median with probability at least 1 - O(n^{-1/4}). For the structural case, this paper proposes an algorithm with O((\\log(n) + w\\log(n/w) log(n)) query complexity, where w is the width of the DAG.", "questions": "-Any previous works studying top-1 selection or k-th item selection? What's the differences between them and the median selection?\n-If we can use more or less strong oracle queries, how many numbers of weak oracle queries will be needed?", "limitations": "No negative social or ethnic concerns", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n-The problem studies in this paper is very interesting and foundational. In a lot of real-world scenarios, querying the same pair multiple times is not possible. This setting differs from the dueling bandit settings, where multiple queries of the same pair can get more and more confidence relations. \n-The algorithms and theoretical analysis are clean and sound. The results look good from my intuition. \n\nWeakness\n-The two problems in this paper do not look very close. Maybe put them into two papers and enrich each paper with more contents and results?\n-The results lack baselines to evaluate. Either previous works or lower bounds can be helpful here.", "was_revised": false, "final_justification": "", "rebuttal": "**Dear Reviewer 2hww,**\n\nThank you for your very positive and encouraging review. We are glad that you found the problem interesting and our analysis clean and sound. Below, we address your specific points in detail.\n\n\n\n**1. On the Two Problems Feeling Disjoint**\n\nWe greatly appreciate your insightful observation, which has helped us recognize a unifying theme across our two problem settings. The key idea is that the *DAG structure can be interpreted as encoding the outcomes of prior strong oracle queries*. This perspective yields a cohesive framework where both settings aim to leverage existing comparison information to minimize the use of costly new queries:\n\n* **Unified Model**\n\n  * *Prior Knowledge Representation*:\n\n    * **DAG edges** = outcomes of historical strong oracle queries (trusted comparisons)\n    * **Weak oracle** = new noisy comparisons (with persistent errors)\n    * **Strong oracle** = new definitive comparisons\n\nWe will add a paragraph in the introduction to explicitly frame this shared motivation and highlight the connection between the two parts of the paper under this unified lens.\n\n\n**2. On the Lack of Baselines and Lower Bounds**\n\nThis is a very important point.\n\n* **Noisy Oracle Setting**:\n  To the best of our knowledge, our work is the first to consider the combination of strong and weak oracles for *exact* median selection. This makes it challenging to find a direct baseline from prior work. However, we agree that discussing theoretical lower bounds would strengthen the paper. One natural lower bound is that *it is not possible to achieve exact selection using only \\$O(n)\\$ weak queries and \\$o(n)\\$ strong queries*—a fact that highlights the necessity of our hybrid design. We will include this discussion in the revision.\n\n* **DAG Setting**:\n  We apologize for not making the baseline clearer. The \"Classic (Mean ±1 std)\" lines in Figure 2 correspond to the performance of the standard median-of-medians algorithm *without access to DAG information*. We will revise the figure captions and clarify this in the main text.\n\n\n**3. Responses to Your Specific Questions**\n\n* **Generalizing to *k*-th Item Selection**:\n  Yes, our algorithm naturally generalizes. In the noisy oracle setting, the key idea is to adjust the rank-based pivot selection. The original algorithm selects pivots \\$d\\$ and \\$u\\$ to form a confidence interval around the median’s expected rank. To target the *k*-th smallest element, we instead center the interval around the expected rank of the *k*-th element in a random sample \\$S\\$ of size \\$r\\$, which is \\$r \\cdot (k/n)\\$. The original success condition, \\$|L| < n/2 < |L| + |M|\\$, is updated to:\n\n  $$\n  |L| < k \\leq |L| + |M|\n  $$\n\n  This ensures that exactly \\$k\\$ elements lie in the union of \\$L\\$ (elements less than the target) and \\$M\\$ (elements near the target). We will add this generalization to the revised manuscript.\n\n\nFor the DAG algorithm (Algorithm 3), the recursive step can search for an element of rank $k$ instead of the median ($n/2$). The algorithm already supports $k$-th element selection, and this functionality is implemented in the supplementary document submitted.\n\n\n\n* **Trade-off Between Strong and Weak Oracles:**\nThis is an excellent and thought-provoking question. The strong oracle is primarily used in two places: (1) to sort the elements in the sample set $R$, and (2) to order the elements in the middle region $M$, i.e., those between the pivots $d$ and $u$. There is an inherent trade-off here: sampling more elements into $R$ reduces the size of $M$, thereby requiring fewer strong oracle comparisons in $M$; conversely, sampling fewer elements increases the burden on the strong oracle to sort a larger $M$. We believe that choosing $\\Theta(\\sqrt{n}poly\\log n)$ elements strikes a balance between these two costs. Consequently, we argue that $\\Theta(\\sqrt{n})$ strong oracle queries are both necessary and sufficient. We will clarify this intuition and include this remark in the revised version.\n\n\nThank you again for your detailed and highly valuable feedback."}, {"review_id": "YhPtQQKfJj", "reviewer": "Reviewer_YZ2f", "summary": "The paper studies the problem of finding the exact median of a set of $n$ elements under two distinct settings – \n1. One has access to a strong (accurate but expensive) oracle along with a weak (inaccurate but inexpensive) oracle. \n2. One has access to a DAG i.e. finding median of a partially ordered set.\n\nFor the first case, the authors introduce a modified LazySelect algorithm that achieves log-linear running time and sublinear number of calls to the strong oracle. For the latter, they present a recursive partitioning algorithm with its complexity depending on the width of the DAG.\n\nThe authors provide theoretical analysis and simulations to support their algorithms.", "questions": "1.\tHow are the two settings related? Can one be smoothly transitioned into another? Would there be any relevance of a joint ‘noisy DAG’ setup?\n2.\tCan you comment on the generalizability of your algorithms to k-th order statistic?\n3.\tOn line 133, shouldn’t it be $O((\\log n)^2)$?\n4.\tWhat would be the worst-case input for your algorithms? What input would they fail to return the median on?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and organized. The algorithms are clearly described and intuitive, and the theoretical analysis is crisp.  \n- The context of the problem and prior works are discussed well, both from the perspective of order statistics of data as well as algorithms with predictions paradigm.\n- Simulations with synthetic data provide a deeper insight into the performance of the algorithms.\n\nWeaknesses:\n- The LazySelect algorithm has been around for a long time and the paper only tweaks it to do an initial filtering based on the weak oracle. \n- For the case of DAGs, the Median of Medians or pivot and partition are commonly used algorithms and their combination with a DAG decomposition suggests limited novelty.\n- The paper also feels disjoint due to a lack of discussion about the similarity and differences of the two settings.", "was_revised": true, "final_justification": "A major shortcoming of the paper was the disjointedness of the two settings discussed. The authors have described a unified framework which ties the paper together. Other minor concerns were adequately answered - k-th statistic generalization, comparison to the original lazy select and worst case settings for their algorithms.\n\nThe authors also outline the novelty of their approach. While I understand their justification, it was still the main reason why I chose to score the paper at 4 - borderline accept rather than a 5 - accept.", "rebuttal": "Dear Reviewer YZ2f,\n\nThank you for your thoughtful feedback and for appreciating the writing, organization, and analysis of our paper. We address your concerns about novelty and the connection between the two settings below.\n\n\n\n**1. On the Novelty of the Algorithms**\n\nWe appreciate your perspective on novelty. While our algorithms build on classic paradigms like LazySelect and pivot-and-partition, our key contributions lie in adapting these paradigms to novel computational models with rigorous theoretical guarantees.\n\nIn the **noisy oracle setting**, we are the first to integrate a **majority vote mechanism within LazySelect** to overcome persistent noise from a weak oracle. This modification enables us to analyze the interplay between weak and strong oracles and to prove that **a sublinear number of strong queries suffices** for exact median selection. To our knowledge, this is the first formal result of this type.\n\nIn the **DAG setting**, our main contribution is connecting the **graph-theoretic structure (DAG width)** to the **comparison complexity** of median selection. This provides a principled way to quantify how much structural side information helps reduce query complexity, yielding the first analysis of median selection in this structured comparison model.\n\nWe will revise the introduction and contributions sections to more clearly emphasize that our novelty lies in:\n(i) the theoretical guarantees for these new models, and\n(ii) the novel use of classical tools (e.g., LazySelect with majority voting) in these contexts.\n\n\n\n**2. On the Two Problems Feeling Disjoint**\n\nWe greatly appreciate your insightful observation, which has helped us recognize a unifying theme across our two problem settings. The key idea is that the **DAG structure can be interpreted as encoding the outcomes of prior strong oracle queries**. This yields a cohesive framework where both settings aim to minimize the number of costly new queries by leveraging existing comparison information.\n\n**Unified Model:**\n\n* **Prior knowledge representation**:\n\n    – **DAG edges** = outcomes of historical strong oracle queries (trusted comparisons)\n\n    – **Weak oracle** = new noisy comparisons (with persistent errors)\n\n    – **Strong oracle** = new definitive comparisons\n\nWe will revise the introduction to explicitly frame this shared motivation and clarify how both settings fit within a unified lens of median selection under side information.\n\n\n**3. On Your Specific Questions**\n\n* **Generalizability to k-th Order Statistic**: Yes, our algorithms can be adapted to find the k-th element by appropriately adjusting the rank thresholds used for pivot selection and final element retrieval.  In the noisy oracle setting, the key idea is to adjust the rank-based pivot selection. The original algorithm selects pivots \\$d\\$ and \\$u\\$ to form a confidence interval around the median’s expected rank. To target the *k*-th smallest element, we instead center the interval around the expected rank of the *k*-th element in a random sample \\$S\\$ of size \\$r\\$, which is \\$r \\cdot (k/n)\\$. The original success condition, \\$|L| < n/2 < |L| + |M|\\$, is updated to:\n\n  $$\n  |L| < k \\leq |L| + |M|\n  $$\n\n  This ensures that exactly \\$k\\$ elements lie in the union of \\$L\\$ (elements less than the target) and \\$M\\$ (elements near the target). We will add this generalization to the revised manuscript.\n\n\nFor the DAG algorithm (Algorithm 3), the recursive step can search for an element of rank $k$ instead of the median ($n/2$). The algorithm already supports $k$-th element selection, and this functionality is implemented in the supplementary document submitted.\n\n\n\n* **Typo on Line 133**: Thank you for pointing this out.\nThe correct bound for $w = O(1)$ is indeed $O(\\log^2 n)$, as can be seen from Theorem 2, which gives a bound of\n$O\\big((\\log n + w \\cdot \\log(n/w)) \\cdot \\log n\\big).$\nHowever, when the DAG width is exactly 1, there is only a single chain and the recursion depth becomes 1. In this case, we can find the exact median using only $O(\\log n)$ comparisons.\nWe will revise the corollary accordingly. The main theorem remains correct as stated.\n\n* **Worst-Case Inputs and Failure Modes**:\n\n   • **Algorithm 1 (Noisy setting)**: The worst case occurs when the random sample $S$ is unrepresentative, leading to poor pivots $d$ and $u$. Combined with adversarial noise from the weak oracle, this can (with low probability) cause the true median to fall outside of the final narrowed region.\n\n   • **Algorithm 2 (DAG setting)**: The worst case is when the DAG has large width $w \\approx n$, offering little help over classical methods. In this case, our algorithm matches the standard comparison complexity up to constants.\n\nWe will include a brief discussion of these cases in the revision.\n\n\nThanks again for your detailed review and constructive suggestions."}]

Author rebuttal:

Meta-review: The paper provides algorithms for median estimation using weak and strong comparison oracles. In the classical setting where no order information is provided, they give an algorithm using quasilinear weak comparisons and sublinear strong comparisons. In the presence of additional partial order information, they obtain better results depending on the partial order "width". 

Overall, reviewers found the problem and solutions natural, and were happy with the provided guarantees. Several reviewers raised many clarifying questions, and while they were largely satisfied by the author responses, their ratings were contingent on the authors adding these clarifications to the submission. The authors should make sure to reread the discussion and edit the final version accordingly.
Decision: Accept (poster)