Median Selection with Noisy and Structural Information

Dear Reviewer 2hww,

Thank 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.

1. On the Two Problems Feeling Disjoint

We 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:

• Unified Model

  • Prior Knowledge Representation:

    • DAG edges = outcomes of historical strong oracle queries (trusted comparisons)
    • Weak oracle = new noisy comparisons (with persistent errors)
    • Strong oracle = new definitive comparisons

We 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.

2. On the Lack of Baselines and Lower Bounds

This is a very important point.

• Noisy Oracle Setting: 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.

• DAG Setting: 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.

3. Responses to Your Specific Questions

• Generalizing to k-th Item Selection: 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:

  $$|L| < k \leq |L| + |M|$$

  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.

For 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.

• Trade-off Between Strong and Weak Oracles: This 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.

Thank you again for your detailed and highly valuable feedback.

Dear Reviewer YZ2f,

Thank 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.

1. On the Novelty of the Algorithms

We 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.

In 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.

In 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.

We will revise the introduction and contributions sections to more clearly emphasize that our novelty lies in: (i) the theoretical guarantees for these new models, and (ii) the novel use of classical tools (e.g., LazySelect with majority voting) in these contexts.

2. On the Two Problems Feeling Disjoint

We 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.

Unified Model:

• Prior knowledge representation:

    – DAG edges = outcomes of historical strong oracle queries (trusted comparisons)

    – Weak oracle = new noisy comparisons (with persistent errors)

    – Strong oracle = new definitive comparisons

We 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.

3. On Your Specific Questions

• 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:

  $$|L| < k \leq |L| + |M|$$

  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.

For 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.

• Typo on Line 133: Thank you for pointing this out. The correct bound for $w = O(1)$ is indeed $O(\log^2 n)$, as can be seen from Theorem 2, which gives a bound of $O\big((\log n + w \cdot \log(n/w)) \cdot \log n\big).$ However, 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. We will revise the corollary accordingly. The main theorem remains correct as stated.

• Worst-Case Inputs and Failure Modes:

   • 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.

   • 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.

We will include a brief discussion of these cases in the revision.

Thanks again for your detailed review and constructive suggestions.

Dear Reviewer NEam,

Thank 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.

1. On the Presentation of the Analysis

We 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.

2. On the Synthetic Nature of Experiments

We 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.

3. Responses to Specific Questions

• Theorem 2 Complexity: Thank you for catching this. The correct bound for $w = O(1)$ is indeed $O(\log^2 n)$, as can be seen from Theorem 2, which gives a bound of $O\big((\log n + w \cdot \log(n/w)) \cdot \log n\big).$ However, 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. We will revise the corollary accordingly. The main theorem remains correct as stated.

• Persistent Weak Oracle Error: 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.

• Relation to Rank Aggregation: 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.

• Algorithm 1, Step 5 (Use of Strong Oracle): 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.

• "True Median" Terminology: 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.

• Lemmas 7 and 9: 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.

• Definition of DAG Width: We will add a formal definition of DAG width (i.e., the size of the largest antichain) in the preliminaries to eliminate ambiguity.

• "Adapts naturally to structured domains...": We agree that this statement can be more concrete. We will revise it to: “The algorithm’s performance, as shown in Theorem 2, improves as the width $w$ of the DAG—representing its structural complexity—decreases.”

Thank you again for your detailed and highly valuable feedback.

I am mostly satisfied by the authors' responses. Still, given the quality of the submission writeup as given, I am not going to increase my score. I think it would be reasonable to accept this paper given the authors' commitments to revision, and otherwise I would be happy to see the revised paper in upcoming submissions.

Dear Reviewer JGL7,

Thank 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.

Addressing Questions

1. Generalization to k-th Largest Element

Yes, 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:

1.1 Adjusting the Pivot Selection

The 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)$.

Modification: The bounds $d$ and $u$ are redefined as:

This 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$.

Here, $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.

1.2 Updating the Success Condition and Final Selection

The original condition for the median, $|L| < n/2 < |L| + |M|$, must be updated for the k-th rank.

Modification: The new success condition becomes:

This ensures that exactly $k$ elements lie in the union of $L$ (less than target) and $M$ (equal to or around the target).

Modification: Once this condition is satisfied, the algorithm sorts the set $M$ and returns the element at position $k - |L|$ in the sorted list.

With 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.

For 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.

2. Reducing Weak Oracle Queries to $O(n)$

We agree this is a fundamental challenge. In fact, we can formally argue that no algorithm can achieve high-probability median selection with only $O(n)$ weak queries (with correctness probability $p = \frac{1}{2} + \epsilon$) and $o(n)$ strong queries, due to two core limitations:

• Weak Oracle Limitation: Previous work showed that using only $O(n)$ weak queries leaves each element misclassified with constant probability, leading to $\Theta(n)$ uncorrected errors.

• Strong Oracle Sparsity: With only $o(n)$ strong queries, we can correct at most $o(n)$ errors. Thus:

  $$\Theta(n) - o(n) = \Theta(n)$$

  errors remain uncorrected, causing median misidentification with probability $1 - o(1)$.

The $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.

Addressing Weaknesses

Weakness #2: Comparison with Original LazySelect

We 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.

Weakness #3: Theorem 2 Corollary

Thank you for pointing out the imprecise phrasing. The correct bound for $w = O(1)$ is indeed $O(\log^2 n)$, as can be seen from Theorem 2, which gives a bound of $O\big((\log n + w \cdot \log(n/w)) \cdot \log n\big).$ However, 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. We will revise the corollary accordingly. The main theorem remains correct as stated.

Weakness #1: Nontriviality of Sublinear Strong Queries

While 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.

Addressing Limitations

Noisy Comparison Algorithm’s Weak Query Usage

The 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.

DAG Algorithm’s Dependence on Width

As 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.

Thank you again for your detailed and highly valuable feedback.