Parallel Algorithms for Select and Partition with Noisy
Comparisons

arXiv:1603.04941v1 [] 16 Mar 2016

Mark Braverman

∗

Jieming Mao

†

S. Matthew Weinberg

‡

March 17, 2016

Abstract
We consider the problem of finding the k th highest element in a totally ordered set of n
elements (Select), and partitioning a totally ordered set into the top k and bottom n − k
elements (Partition) using pairwise comparisons. Motivated by settings like peer grading
or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons
may be inconsistent with the ground truth, we evaluate algorithms based both on their total
runtime and the number of interactive rounds in three comparison models: noiseless (where the
comparisons are correct), erasure (where comparisons are erased with probability 1 − γ), and
noisy (where comparisons are correct with probability 1/2 + γ/2 and incorrect otherwise). We
provide numerous matching upper and lower bounds in all three models. Even our results in
the noiseless model, which is quite well-studied in the TCS literature on parallel algorithms, are
novel.

∗

Department of Computer Science, Princeton University, email: mbraverm@cs.princeton.edu. Research supported
in part by an NSF CAREER award (CCF-1149888), NSF CCF-1215990, NSF CCF-1525342, a Packard Fellowship
in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry.
†
Department of Computer Science, Princeton University, email: jiemingm@cs.princeton.edu.
‡
Department of Computer Science, Princeton University, email: sethmw@cs.princeton.edu. Research completed
in part while the author was a Microsoft Research Fellow at the Simons Institute for the Theory of Computing.

0

1

Introduction

Rank aggregation is a fundamental problem with numerous important applications, ranging from
well-studied settings such as social choice [CN91] and web search [DKNS01] to newer platforms
such as crowdsourcing [CBCTH13] and peer grading [PHC+ 13]. Salient common features among
these applications is that in the end, ordinal rather than cardinal information about the elements is
relevant, and a precise fine-grained ordering of the elements is often unnecessary. For example, the
goal of social choice is to select the best alternative, regardless of how good it is. In a curved course,
the goal of peer grading is to partition assignments into quantiles corresponding to A/B/C/D, etc,
regardless of their absolute quality.
Prior work has produced numerous ordinal aggregation procedures (i.e. based on comparisons
of elements rather than cardinal evaluations of individual elements) in different settings, and we
overview those most relevant to our work in Section 1.1. However, existing models from this
literature fail to capture an important aspect of the problem with respect to some of the newer
applications; that multiple rounds of interaction are costly. In crowdsourcing, for instance, one
round of interaction is the time it takes to send out a bunch of tasks to users and wait for their
responses before deciding which tasks to send out next, which is the main computational bottleneck.
In peer grading, each round of interaction might take a week, and grades are expected to be
determined certainly within a few weeks. In conference decisions, even one round of interaction
seems to be pushing the time constraints.
Fortunately, the TCS community already provides a vast literature of algorithms with this
constraint in mind, under the name of parallel algorithms. For instance, previous work resolves
questions like “how many interactive rounds are necessary for a deterministic or randomized algorithm to select the kth element with O(n) total comparisons?” [Val75, Rei81, AKSS86, AA88a,
AA88b, BB90]. This line of research, however, misses a different important aspect related to these
applications (that is, in fact, captured by most works in rank aggregation), that the comparisons
might be erroneous. Motivated by applications such as crowdsourcing and peer grading, we therefore study the round complexity of Partition, the problem of partitioning a totally ordered set
into the top k and bottom n − k elements, when comparisons might be erroneous.
Our first results on this front provide matching upper and lower bounds on what is achievable for
Partition in just one round in three different models of error: noiseless (where the comparisons
are correct), erasure (where comparisons are erased with probability 1 − γ), and noisy (where
comparisons are correct with probability 1/2 + γ/2 and incorrect otherwise). We provide oneround algorithms using dn comparisons that make O(n/d), O(n/(dγ)), and O(n/(dγ 2 )) mistakes
(a mistake is any element placed on the wrong side of the partition) with high probability in
the three models, respectively. The algorithms are randomized and different for each model, and
the bounds hold both when d is an absolute constant or a function of n and γ. We provide
asymptotically matching lower bounds as well: all (potentially randomized) one-round algorithms
using dn comparisons necessarily make Ω(n/d), Ω(n/(dγ)), and Ω(n/(dγ 2 )) mistakes in expectation
in the three models, respectively. We further show that the same algorithms and lower bound
constructions are also optimal (up to absolute constant factors) if mistakes are instead weighted by
various different measures of their distance to k, the cutoff.1
1

Specifically, if WRONGi denotes the random variable thatPis 1 if an algorithm misplaces i and 0 otherwise, we
c
consider measures of the following form, for any choice of c:
i WRONGi |i − k| . For example, c = 0 counts the
number of mistakes. This is further discussed in Section 2.

After understanding completely the tradeoff between the number of comparisons and mistakes
for one-round algorithms in each of the three models, we turn our attention to multi-round algorithms. Here, the results are more complex and can’t be summarized in a few sentences. We briefly
overview our multi-round results in each of the three models below. Again, all of the upper and
lower bounds discussed below extend when mistakes are weighted by their distance to the cutoff.
We overview the techniques used in proving our results in Section 1.2, but just briefly note here that
the level of technicality roughly increases as we go from the noiseless to erasure to noisy models.
In particular, lower bounds in the noisy model are quite involved.
Multi-Round Results in the Noiseless Model.
1. We design a 2-round algorithm for Partition using n/ε total comparisons that makes
O(n1/2+ε poly(log n))) mistakes with probability 1 − e−Ω(n) , and prove a nearly matching
√
lower bound of Ω( n · ε5/2 ) mistakes, for any ε > 0 (ε may be a constant or a function of n).
2. We design a 3-round algorithm for Partition making O(n · poly(log n)) total comparisons
that makes zero mistakes with probability 1−e−Ω(n) . It is known that ω(n) total comparisons
are necessary for a 3-round algorithm just to solve Select, the problem of finding the kth
element, with probability 1 − o(1) [BB90].
3. We design a 4-round algorithm for Partition making O(n) total comparisons that makes zero
mistakes with probability 1 − e−Ω(n) . This matches the guarantee provided by an algorithm
of Bollobás and Brightwell for Select, but is significantly simpler (in particular, it avoids
any graph theory) [BB90].
Multi-Round Results in the Erasure Model.
1. We design a O(log∗ (n))-round algorithm for Partition making O(n/γ) total comparisons
that makes zero mistakes with probability 1 − e−Ω(n) .
2. We show that no o(log∗ (n))-round algorithm even for Select making O(n/γ) total comparisons can succeed with probability 2/3.
Multi-Round Results in the Noisy Model.
1. We design a 4-round algorithm for Partition making O(n log n/γ 2 ) comparisons that makes
zero mistakes with high probability (a trivial corollary of our noiseless algorithm).
2. We show that no algorithm even for Select making o(n log n/γ 2 ) comparisons can succeed
with probability 2/3 (in any number of rounds).
3. We design an algorithm for findMin (the special case of Select with k = n) making
O(n/γ 2 ) comparisons that succeeds with probability 2/3. We also show that no algorithm
making o(n log n/γ 2 ) comparisons can solve findMin with probability 1 − 1/poly(n) (in any
number of rounds).
Together, these results tell an interesting story. In one round, one can obtain the same guarantee
in the noiseless versus erasure model with an additional factor of 1/γ comparisons. And one can
obtain the same guarantee in the erasure versus noisy model with an additional factor of 1/γ
comparisons. In some sense, this should be expected, because this exactly captures the degradation
in information provided by a single comparison in each of the three models (a noiseless comparison
provides one bit of information, an erasure comparison provides γ bits of information, and a noisy
comparison provides Θ(γ 2 ) bits of information). But in multiple rounds, everything changes. In
2

four rounds, one can perfectly partition with high probability and O(n) total comparisons in the
noiseless model. In the erasure model, one can indeed partition perfectly with high probability and
O(n/γ) comparisons, but now it requires Θ(log∗ (n)) rounds instead of just 4. Moreover, in the noisy
model, any algorithm even solving Select with probability 2/3 requires an Ω(log n/γ) blow-up in
the number of comparisons, in any number of rounds! Note that neither of these additional factors
come from the desire to succeed with high probability (as the lower bounds hold against even a 2/3
success) nor the desire to partition every element correctly (as the lower bounds hold even for just
Select), but just from the way in which interaction helps in the three different models.
While we believe that the story told by our work as a whole provides the “main result,” it is
also worth emphasizing independently our results in the noisy model. Our one-round algorithm,
for instance, is more involved than its counterparts in the noiseless and erasure models and our
analysis uses the theory of biased random walks. Our multi-round lower bounds against Select and
findMin in the noisy model are the most technical results of the paper, and tell their own interesting
story about the difference between findMin and Select in the noisy model. To our knowledge,
most tight lower bounds known for Select come directly from lower bounding findMin. It’s
surprising that findMin requires Θ(log n) fewer comparisons than Select to solve with probability
2/3 in the noisy model.
We proceed now by discussing some related works below, and briefly overviewing our techniques
in Section 1.2. We provide some conclusions and future directions in Section 1.3. Our single-round
results are discussed in Section 3 and our multi-round results are discussed in Section 4. However,
due to space constraints, all proofs are deferred to the appendix.

1.1

Related Work

Rank aggregation is an enormous field that we can’t possibly summarize in its entirety here. Some
of the works most related to ours also study Partition (sometimes called Top-K). Almost all
of these works also consider the possibility of erroneous comparisons, although sometimes under
different models where the likelihood of an erroneous comparison scales with the distance between
the two compared elements [CS15, BSC+ 13, Eri13]. More importantly, to our knowledge this line
of work either considers settings where the comparisons are exogenous (the designer has no control
over which comparisons are queried, she can just analyze the results), or only analyze the query
complexity and not the round complexity of designed algorithms. Our results contribute to this line
of work by providing algorithms designed for settings like crowdsourcing or peer grading where the
designer does have design freedom, but may be constrained by the number of interactive rounds.
There is a vast literature from the parallel algorithms community studying various sorting
and selection problems in the noiseless model. For instance, tight bounds are known on the
round complexity of Select for deterministic algorithms using O(n) total comparisons (it is
Θ(log log n)) [Val75, AKSS86], and randomized algorithms using O(n) total comparisons (it is
4) [AA88b, AA88a, Rei81, BB90]. Similar results are known for sorting and approximate sorting
as well [Col88, AAV86, AKS83, HH81, BT83, BH85, Lei84]. Many of the designed deterministic
algorithms provide sorting networks. A sorting network on n elements is a circuit whose gates are
binary comparators. The depth of a sorting network is the number of required rounds, and the
number of gates is the total number of comparisons. Randomized algorithms are known to require
fewer rounds than deterministic ones with the same number of total comparisons for both sorting
and selecting [AA88a, BB90].
In the noisy model, one can of course take any noiseless algorithm and repeat every comparison
3

O(log n/δ2 ) times in parallel. To our knowledge, positive results that avoid this simple repetition
are virtually non-existent. This is likely because a lower bound of Leighton and Ma [LM00] proves
that in fact no sorting network can provide an asymptotic improvement (for complete sorting), and
our lower bound (Theorem 11) shows that no randomized algorithm can provide an asymptotic
improvement for Select. To our knowledge, no prior work studies parallel sorting algorithms in
the erasure model. On this front, our work contributes by addressing some open problems in the
parallel algorithms literature, but more importantly by providing the first parallel algorithms and
lower bounds for Select in the erasure and noisy models.
There is also an active study of sorting in the noisy model [BM08, BM09, MMV13] within
the TCS community without concern for parallelization, but with concern for resampling. An
algorithm is said to resample if it makes the same comparison multiple times. Clearly, an algorithm
that doesn’t resample can’t possibly find the median exactly in the noisy model (what if the
comparison between n/2 and n/2 + 1 is corrupted?). The focus of these works is designing polytime algorithms to find the maximum-likelihood ordering from a set of n2 noisy comparisons.
Our

n
work is fundamentally different from these, as we have asymptotically fewer than 2 comparisons
to work with, and at no point do we try to find a maximum-likelihood ordering (because we only
want to solve Partition).

1.2

Tools and Techniques

Single Round Algorithms and Lower Bounds. Our single round results are guided by the
following surprisingly useful observation: in order for an algorithm to possibly know that i exceeds
the kth highest element, i must at least be compared to some element between itself and k (as
otherwise, the comparison results would be identical if we replaced i with an element just below
k). Unsurprisingly, it is difficult to guarantee that many elements within n/d of k are compared
to elements between themselves and k using only dn total comparisons in a single round, and this
forms the basis for our lower bounds. Our upper bounds make use of this observation as well, and
basically are able to guarantee that an element is correctly placed with high probability whenever
it is compared to an element between itself and k. It’s interesting that the same intuition is key
to both the upper and lower bounds. We provide a description of the algorithms and proofs in
Section 3.
In the erasure model, the same intuition extends, except that in order to have a non-erased
comparison between i and an element between i and k, we need to make roughly 1/γ such comparisons. This causes our lower bounds to improve by a factor of 1/γ. In the noisy model, the
same intuition again extends, although this time the right language is that we need to learn Ω(1)
bits of information from comparisons of i to elements between i and k, which requires Ω(1/γ 2 )
such comparisons, and causes the improved factor of 1/γ 2 in our lower bounds. Our algorithms in
these two models are similar to the noiseless algorithm, but the analysis becomes necessarily more
involved. For instance, our analysis in the noisy model appeals to facts about biased random walks
on the line.
Multi-Round Algorithms and Lower Bounds. Our constant-round algorithms in the noiseless model are based on the following intuition: once we reach the point that we are only uncertain
about o(n) elements, we are basically looking at a fresh instance of Partition on a significantly
smaller input size, except we’re still allowed Θ(n) comparisons per round. Once we’re only un√
certain about only O( n) elements, one additional round suffices to finish up (by comparing each
4

element to every other one). The challenge in obtaining a four-round algorithm (as opposed to
just an O(1)-round algorithm) is ensuring that we make significant enough gains in the first three
rounds.
Interestingly, these ideas for constant-round algorithms in the noiseless model don’t prove useful
in the erasure or noisy models. Essentially the issue is that even after a constant number of rounds,
we are unlikely to be confident that many elements are above or below k, so we can’t simply recurse
on a smaller instance. Still, it is quite difficult to discover a formal barrier, so our multi-round lower
bounds for the erasure and noisy models are quite involved. We refer the reader to Section 4 for
further details.

1.3

Conclusions

We study the problems of Partition and Select in settings where interaction is costly in the
noiseless, erasure, and noisy comparison models. We provide matching (up to absolute constant
factors) upper and lower bounds for one round algorithms in all three models, which also show that
the number of comparisons required for the same guarantee degrade proportional to the information
provided by a single comparison. We also provide matching upper and lower bounds for multi-round
algorithms in all three models, which also show that the round and query complexity required for
the same guarantee in these settings degrades worse than just by the loss in information when
moving between the three comparison models. Finally, we show a separation between findMin
and Select in the noisy model.
We believe our work motivates two important directions for future work. First, our work considers some of the more important constraints imposed on rank aggregation algorithms in applications
like crowdsourcing or peer grading, but not all. For instance, some settings might require that
every submission receives the same amount of attention (i.e. is a member of the same number of
comparisons), or might motivate a different model of error (perhaps where mistakes aren’t independent or identical across comparisons). It would be interesting to design algorithms and prove
lower bounds under additional restrictions motivated by applications.
Finally, it is important to consider incentives in these applications. In peer grading, for instance,
the students themselves are the ones providing the comparisons. An improperly designed algorithm
might provide “mechanism design-type” incentives for the students to actively misreport if they
think it will boost their own grade. Additionally, there are also “scoring rule-type” incentives that
come into play: grading assignments takes effort! Without proper incentives, students may choose
to put zero or little effort into their grading and just provide random information. We believe
that using ordinal instead of cardinal information will be especially helpful on this front, as it is
much easier to design mechanisms when players just make binary decisions, and it’s much easier
to understand how the noisy information provided by students scale with effort (in our models,
it is simply that γ will increase with effort). It is therefore important to design mechanisms for
applications like peer grading by building off of our algorithms.

2

Preliminaries and Notation

In this work, we study two problems, Select and Partition. Both problems take as input a
randomly sorted, totally ordered set and an integer k. For simplicity of notation, we denote the ith
smallest element of the set as i. So if the input set is of size n, the input is exactly [n]. In Select,

5

the goal is to output the (location of the) element k. In Partition, the goal is to partition the
elements into the top k, which we’ll call A for Accept and the bottom n − k, which we’ll call R for
Reject. Also for ease of notation, we’ll state all of our results for k = n/2, the median, w.l.o.g.2
We say an algorithm solves Select if it outputs the median, and solves Partition if it places
correctly all elements above and below the median. For Select, we will say that an algorithm is a
t-approximation with probability p if it outputs an element in [n/2 − t, n/2 + t] with probability at
least p. For Partition, we will consider a class of success measures, parameterized by a constant
c,
error associated with a specific partitioning into A ⊔ R is equal to
P and say the c-weighted
P
c+
c 3
I(i
∈
R)i
i>n/2
i<n/2 I(i ∈ A)i . Interestingly, in all cases we study, the same algorithm is
asymptotically optimal for all c.
Query and Round Complexity. Our algorithms will be comparison-based. We study both the
number of queries, and the number of adaptive rounds necessary to achieve a certain guarantee.4
We may not always emphasize the runtime of our algorithms, but they all run in time poly(n).
Notation. We always consider settings where the input elements are a priori indistinguishable, or
alternatively, that our algorithms randomly permute the input before making comparisons. When
we write x < y, we mean literally that x < y in the ground truth. In the noisy model, the results
of comparisons may disagree with the underlying ordering, so we say that x beats y if a noisy
comparison of x and y returned x as larger than y (regardless of whether or not x > y).
Models of Noise. We consider three comparison models, which return the following when a > b.
• Noiseless: Returns a beats b.
• Erasure: Returns a beats b with probability γ, and ⊥ with probability 1 − γ.
• Noisy: Returns a beats b with probability 1/2+ γ/2, and b beats a with probability 1/2− γ/2.
Partition versus Select. We design all of our algorithms for Partition, and prove all of our
lower bounds against Select. We do this because Select is in some sense a strictly easier problem
than Partition. We discuss how one can get algorithms for Select via algorithms for Partition
and vice versa formally in Appendix A.
Resampling. Finally, note that in the erasure and noisy models, it may be desireable to query
the same comparison multiple times. This is called resampling. It is easy to see that without
resampling, it is impossible to guarantee that the exact median is found with high probability,
even when all n2 comparisons are made (what if the comparison between n/2 and n/2 + 1 is
corrupted?). Resampling is not necessarily undesireable in the applications that motivate this
work, so we consider our main results to be in the model where resampling is allowed. Still, it turns
out that all of our algorithms can be easily modified to avoid resampling at the (necessary) cost of
2

We show formally in Appendix A that this is indeed w.l.o.g.
For instance, c = 0 counts the number of mistakes. c = 1 counts the number of mistakes, weighted by the distance
of the mistaken element from the median. c = 2 is similar to mean-squared-error, etc.
4
For example, an algorithm that makes Q queries one at a time, waiting for the result of previous queries before
deciding which queries to make next has round complexity Q. An algorithm that makes all queries up front, without
knowing any results has round complexity 1. We call protocols with round complexity 1 non-adaptive.
3

6

a small additional error, and it is easy to see the required modifications.5 All of our lower bounds
hold even against algorithms that resample.

3

Results for Non-Adaptive Algorithms

In this section, we provide our results on non-adaptive (round complexity = 1) algorithms. We
begin with the upper bounds below, followed by our matching (up to constant factors) lower bounds.

3.1

Upper Bounds

We provide asymptotically optimal algorithms in each of the three comparison models. Our three
algorithms actually choose the same comparisons to make, but determine whether or not to accept
or reject an element based on the resulting comparisons differently. The algorithms pick a skeleton
√
set S of size n and compare every element in S to every other element. Each element not in S is
compared to d − 1 random elements of S. Pseudocode for this procedure is given in Appendix B.
From here, the remaining task in all three models is similar: the algorithm must first estimate
the rank of each element in the skeleton set. Then, for each i, it must use this information combined
with the results of d − 1 comparisons to guess whether i should be accepted or rejected. The correct
approach differs in the three models, which we discuss next.
Noiseless Model. Pseudocode for our algorithm in the noiseless model is provided as Algorithm 2
in Appendix B. First, we estimate that the median of the skeleton set, x, is close to the actual
median. Then, we hope that each i ∈
/ S is compared to some element in S between itself and x. If
this happens, we can pretty confidently accept or reject i. If it doesn’t, then all we learn is that i
is beaten by some elements above x and it beats some elements below x, which provides no helpful
information about whether i is above or below the median, so we just make a random decision.
Theorem 1. Algorithm 2 has query complexity dn, round complexity 1, does not resample, and
outputs a partition that, for all c, has:
• expected c-weighted error O((n/d)c+1 ), for any d = o(n1/4 )
3
2c+2 )
• c-weighted error O((n/d)c+1 ) with probability 1 − e−Ω(n /d
, for any d = o(n1/4 ).
We provide a complete proof of Theorem 1 in Appendix B. The main ideas are the following.
There are two sources of potential error in Algorithm 2. First, maybe the skeleton set is poorly
chosen and not representative of the ground set. But this is extremely unlikely with such a large
skeleton set. Second, note that if i is compared to any element in S between itself and x, and x is
very close to n/2, then i will be correctly placed. If |i − n/2| > n/d, then we’re unlikely to miss
this window on d − 1 independent tries, and i will be correctly placed.
Erasure Model. In the erasure model, pseudocode for the complete algorithm we use is Algorithm 3 in Appendix B. At a high level, the algorithm is similar to Algorithm 2 for the noiseless
model, so we refer the reader to Appendix B to see the necessary changes.
Theorem 2. Algorithm 3 has query complexity dn, round complexity 1, does not resample, and
outputs a partition that, for all c, has:
5

Essentially, replace all resampled comparisons with comparisons to “nearby” elements instead.

7

• expected c-weighted error O((n/(dγ))c+1 ), for any d, γ such that d/γ = o(n1/4 )
√
3
2c+2 )
• c-weighted error O((n/(dγ))c+1 ) with probability 1−e−Ω(n /d
, whenever d/γ = o( n) and
dγ = o(n1/4 ).
We again postpone a complete proof of Theorem 2 to Appendix B. The additional ingredient
beyond the noiseless case is a proof that with high probability, not too many of the comparisons
within S are erased and therefore while we can’t learn the median of S exactly, we can learn a
set of almost |S|/2 elements that are certainly above the median, and almost |S|/2 elements that
are certainly below. If i ∈
/ S beats an element that is certainly above the median of S, we can
confidently accept it, just like in the noiseless case.
Noisy Model. Pseudocode for our algorithm in the noisy model is provided as Algorithm 4 in
Appendix B. Algorithm 4 is necessarily more involved than the previous two. We can still recover
a good ranking of the elements in the skeleton set using the Braverman-Mossel algorithm [BM08],
so this isn’t the issue. The big difference between the noisy model and the previous two is that no
single comparison can guarantee that i ∈
/ S should be accepted or rejected. Instead, every time we
have a set of elements all above the median of S, x, of which i beats at least half, this provides some
evidence that i should be accepted. Every time we have a set of elements all below x of which i is
beaten by at least half, this provides some evidence that i should be rejected. The trick is now just
deciding which evidence is stronger. Due to space constraints, we refer the reader to Algorithm 4
to see our algorithm, which we analyze using theory from biased random walks on the line.
Theorem 3. Algorithm 4 has query complexity dn, round complexity 1, does not resample, and
outputs a partition that, for all c, has:
• expected c-weighted error O((n/(dγ 2 ))c+1 ), for any d = o(n1/4 ), γ = ω(n1/8 ).
3
2c+2 )
• c-weighted error O((n/(dγ 2 ))c+1 ) with probability 1 − eΩ(n /d
, for any d = o(n1/4 ), γ =
1/8
ω(n ).

3.2

Lower Bounds

In this section, we show that the algorithms designed in the previous section are optimal up to
constant factors. All of the algorithms in the previous section are “tight,” in the sense that we
expect element i to be correctly placed whenever it is compared to enough elements between itself
and the median. In the noiseless model, one element is enough. In the erasure model, we instead
need Ω(1/γ) (to make sure at least one isn’t erased). In the noisy model, we need Ω(1/γ 2 ) (to make
sure we get Ω(1) bits of information about the difference between i and the median). If we don’t
have enough comparisons between i and elements between itself and the median, we shouldn’t hope
to be able to classify i correctly, as the comparisons involving i would look nearly identical if we
replaced i with an element just on the other side of the median. Our lower bounds capture this
intuition formally, and are all proved in Appendix B.
Theorem 4. For all c, d > 0, any non-adaptive algorithm with query complexity dn necessarily has
expected c-weighted error Ω((n/d)c+1 ) in the noiseless model, Ω((n/(dγ))c+1 ) in the erasure model,
and Ω((n/(dγ 2 ))c+1 ) in the noisy model.

8

4

Results for Multi-Round Algorithms

4.1

Noiseless Model

We first present our algorithm and nearly matching lower bound for 2-round algorithms. The first
round of our algorithm tries to get as good of an approximation to the median as possible, and then
compares it to every element in round two. Getting the best possible approximation is actually
√
a bit tricky. For instance, simply finding the median of a skeleton set of size n only guarantees
an element within Θ(n3/4 ) of the median.6 We instead take several “iterations” of nested skeleton
sets to get a better and better approximation to the median. In reality, all iterations happen
simultaneously in the first round, but it is helpful to think of them as sequential refinements.
For any r ≥ 1, our algorithm starts with a huge skeleton set S1 of n2r/(2r+1) random samples
from [n]. This is too large to compare every element in S1 with itself, so we choose a set T1 ⊆ S1 of
n1/(2r+1) random pivots. Then we compare every element in S1 to every element in T1 , and we will
certainly learn two pivots, a1 and b1 such that the median of S1 lies in [a1 , b1 ], and a p1 such that
the median of S1 is exactly the (p1 |A1 |)th element of A1 = S1 ∩ [a1 , b1 ]. Now, we recurse within
A1 and try to find the (p1 |A1 |)th element. Of course, because all of these comparisons happen
in one round, we don’t know ahead of time in which subinterval of S1 we’ll want to recurse, so
we have to waste a bunch of comparisons. These continual refinements still make some progress,
and allow us to find a smaller and smaller window containing the median of S1 , which is a very
good approximation to the true median because S1 was so large. Pseudocode for our algorithm is
Algorithm 5 in Appendix C, which “recursively” tries to find the (pi |Ai |)th element of Ai .
Theorem 5. For all c, r and ε > 0, Algorithm 5 has round complexity 2, query complexity (r + 1)n,
and outputs a partition that:
• has expected c-weighted error at most (8rn(r+1)/(2r+1)+ε )c+1
Ω(ε)

• has c-weighted error at most (8rn(r+1)/(2r+1)+ε )c+1 with probability at least 1 − re−n .
Note that setting r = log n, and ε such that nε = 8 log3 n, we get an algorithm with round com√
plexity 2, query complexity n log n+n that outputs a partition with c-weighted error O(( n log4 n)c+1 )
with probability 1 − O(log n/n2 ).
We also prove a nearly matching lower bound on two-round algorithms in the noiseless model.
At a very high level, our lower bound repeats the argument of our one round lower bound twice.
Specifically, we show that after one round, there are many elements within a window of size Θ(n/d)
of the median such that a constant fraction of these elements have not been compared to any other
elements in this window. We then show that after the second round, conditioned on this, there is
√
necessarily a window of size ≈ n such that a constant fraction of these elements have not been
compared to any other elements in this window. Finally we show that this implies that we must
err on a constant fraction of these elements. The actual proof is technical, but follows this high
level outline. Proofs of Theorems 5 and 6 can be found in Appendix C.
Theorem 6. For all c, and any d = o(n1/5 ), any algorithm with query complexity dn and round
√
complexity 2 necessarily has expected c-weighted error Ω(( n/d5/2 )c+1 ).
6

This is exactly what Bollobás and Brightwell do in the first round of their 4-round algorithm, which is why
sophisticated graph theory follows to fit into four rounds. Our improved first round simplifies the remaining rounds.

9

From here we show how to make use of our two-round algorithm to design a three-round
algorithm that makes zero mistakes with high probability. After our two-round algorithm with
appropriate parameters, we can be pretty sure that the median lies somewhere in a range of
√
O( n log4 n), so we can just compare all of these elements to each other in one additional round.
Pseudocode for Algorithm 6 is in Appendix C.
Theorem 7. For all c, Algorithm 6 has query complexity O(n log8 n), round complexity 3, and
outputs a partition with zero c-weighted error with probability 1 − O(log n/n2 ).
Again, recall that ω(n) queries are necessary for any three-round algorithm just to solve Select
with probability 1−o(1) [BB90]. Finally, we further make use of ideas from our two-round algorithm
to design a simple four round algorithm that has query complexity O(n) and makes zero mistakes
with high probability. More specifically, we appropriately tune the parameters for our two-round
algorithm (i.e. set r = 1) to find a window of size ≈ n2/3 that contains the median (and already
correctly partition all other elements). We then use similar ideas in round three to further find a
√
window of size ≈ n that contains the median (and again correctly partition all other elements).
We use the final round to compare all remaining uncertain elements to each other and correctly
partition them.
Theorem 8. For all c, and any ε ∈ (0, 1/18), Algorithm 7 has query complexity O(n), round
ε
complexity 4, and outputs a partition with zero c-weighted error with probability at least 1 − e−Ω(n ) .

4.2

Erasure and Noisy Models

Here we briefly overview our results on multi-round algorithms in the erasure and noisy models.
We begin with an easy reduction from these models to the noiseless model, at the cost of a blowup in the round or query complexity. Essentially, we are just observing that one can adaptively
resample any comparison in the erasure model until it isn’t erased (which will take 1/γ resamples
in expectation), and also that one can resample in parallel any comparison in either the erasure or
noisy model the appropriate number of times and have it effectively be a noiseless comparison.
Proposition 1. If there is an algorithm solving Partition, Select or findMin in the noiseless
model with probability p that has query complexity Q and round complexity r, then there are also
algorithms that resample that:
• solve Partition, Select or findMin in the erasure model with probability p that have
expected query complexity Q/γ, but perhaps with expected round complexity Q/γ as well.
• solve Partition, Select or findMin in the erasure model with probability p − 1/poly(n)
that have query complexity O(Q(log Q + log n)/γ), and round complexity r.
• solve Partition, Select or findMin in the noisy model with probability p − 1/poly(n) that
have query complexity O(Q(log Q + log n)/γ 2 ), and round complexity r.
Corollary 1. There are algorithms that resample that:
• solve Partition or Select in the erasure model with probability 1 with expected query complexity O(n/γ) (based on the QuickSelect or Median-of-Medians algorithm [Hoa61, BFP+ 73]).
• solve Partition or Select in the erasure model with probability 1 − 1/poly(n) with query
complexity O(n log n/γ) and round complexity 4.

10

• solve Partition or Select in the noisy model with probability 1 − 1/poly(n) with query
complexity O(n log n/γ 2 ) and round complexity 4.
In the erasure model, the algorithms provided by this reduction do not have the optimal
round/query complexity. We show that Θ(n/γ) queries are necessary and sufficient, as well as
Θ(log∗ (n)) rounds. For the algorithm, we begin by finding the median of a random set of size
n/ log n elements. This can be done in 4 rounds and O(n/δ) total comparisons by Corollary 1.
Doing this twice in parallel, we find two elements that are guaranteed to be above/below the median, but very close. Then, we spend log∗ (n) rounds comparing every element to both of these.
It’s not obvious that this can be done in log∗ (n) rounds. Essentially what happens is that after
each round, a fraction of elements are successfully compared, and we don’t need to use any future
comparisons on them. This lets us do even more comparisons involving the remaining elements
in future rounds, so the fraction of successes actually increases with successive rounds. Analysis
shows that the number of required rounds is therefore log∗ (n) (instead of log(n) if the fraction was
constant throughout all rounds). After this, we learn for sure that the median lies within a sublinear window, and we can again invoke the 4-round algorithm of Corollary 1 to finish up. Our lower
bound essentially shows that it takes log∗ (n) rounds just to have a non-erased comparison involving
all n elements even with O(n/δ) per round, and that this implies a lower bound. Pseudocode for
the algorithm and proofs of both theorems are in Appendix D.
Theorem 9. With probability at least 1 − 1/poly(n), Algorithm 9 has query complexity O(n/γ),
round complexity log∗ (n) + 8, and solves Partition.
Theorem 10. Assume γ ≤ 1/2. In the erasure model, any algorithm solving Select with probability 2/3 even with O(n/γ) comparisons per round necessarily has round complexity Ω(log∗ (n)).
We now introduce a related problem that is strictly easier than Partition or Select, which we
call Rank, and prove lower bounds on the round/query complexity of Rank noisy models, which
will imply lower bounds on Partition and Select. In Rank, we are given as input a set S of n
elements, and a special element b and asked to determine b’s rank in S (i.e. how many elements
in S are less than b).7 We say that a solution is a t-approximation if the guess is within t of the
element’s actual rank. We show formally that Rank is strictly easier than Select in Appendix A.
From here, we prove lower bounds against Rank in the noisy model.
At a high level, we show (in the proof of Theorem 11) that with only O(n log n/γ 2 ) queries, it’s
very likely that there are a constant fraction of ai ’s such that the algorithm is can’t be very sure
about the relation between ai and b. This might happen, for instance, if not many comparisons were
done between ai and b and they were split close to 50-50. From here, we use an anti-concentration
inequality (the Berry-Essen inequality) to show that the rank of b does not concentrate within
some range of size Θ(n3/8 ) conditioned on the available information. In otherwords, the information
available simply cannot narrow down the rank of b to within a small window with decent probability,
no matter how that information is used. We then conclude that no algorithms with o(n log n/γ 2 )
comparisons can approximate the rank well with probability 2/3.
Theorem 11. In the noisy model, any algorithm obtaining an (n3/8 /40)-approximation for Rank
with probability 2/3 necessarily has query complexity Ω(n log n/γ 2 ).
7

A more formal statement of Rank is in the proof of Proposition 4 in Appendix D.

11

Finally, we conclude with an algorithm for findMin in the noisy model showing that findMin
is strictly easier than Select. This is surprising, as most existing lower bounds against Select
are obtained by bounding findMin. Our algorithm again begins by finding the minimum, x, of a
random set of size n/ log n using O(n/γ 2 ) total comparisons by Corollary 1. Then, we iteratively
compare each element to x a fixed number of times, throwing out elements that beat it too many
times. Again, as we throw out elements, we get to compare the remaining elements to x more and
more. We’re able to show that after only an appropriate number of iterations (so that only O(n/δ2 )
total comparisons have been made), it’s very likely that only n/ log n elements remain, and that
with constant probability the true minimum was not eliminated. From here, we can again invoke
the algorithm of Corollary 1 to find the true minimum (assuming it wasn’t eliminated).
Theorem 12. Assume n is large enough and 10 ≤ c ≤ log n. Algorithm 10 has query complexity
3cn
and solves findMin in the noisy model with probability at least 1 − e−Ω(c) .
γ2
Theorem 13. Assume c ≥ 1, n is large enough and γ ≤ 1/4. Any algorithm in the noisy model
with query complexity γcn2 solves findMin with probability at most 1 − e−O(c) .
Theorem 12 shows that findMin is strictly easier than Select (as it can be solved with constant
probability with asymptotically fewer comparisons). Theorem 13 is included for completeness, and
shows that it is not possible to get a better success probability without a blow-up in the query
complexity. The proof of Theorem 13 is similar to that of Theorem 11.

12

References
[AA88a]

Noga Alon and Yossi Azar. The average complexity of deterministic and randomized
parallel comparison-sorting algorithms. SIAM J. Comput., 17(6):1178–1192, 1988. 1,
1.1

[AA88b]

Noga Alon and Yossi Azar. Sorting, approximate sorting, and searching in rounds.
SIAM J. Discrete Math., 1(3):269–280, 1988. 1, 1.1

[AAV86]

Noga Alon, Yossi Azar, and Uzi Vishkin. Tight complexity bounds for parallel comparison sorting. In 27th Annual Symposium on Foundations of Computer Science,
Toronto, Canada, 27-29 October 1986, pages 502–510, 1986. 1.1

[AKS83]

Miklós Ajtai, János Komlós, and Endre Szemerédi. An o(n log n) sorting network.
In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27
April, 1983, Boston, Massachusetts, USA, pages 1–9, 1983. 1.1

[AKSS86]

M Ajtai, J Komlos, W L Steiger, and E Szemeredi. Deterministic selection in o(loglog
n) parallel time. In Proceedings of the Eighteenth Annual ACM Symposium on Theory
of Computing, STOC ’86, pages 188–195, New York, NY, USA, 1986. ACM. 1, 1.1

[BB90]

Béla Bollobás and Graham Brightwell. Parallel selection with high probability. SIAM
J. Discrete Math., 3(1):21–31, 1990. 1, 2, 3, 1.1, 4.1

[BFP+ 73]

Manuel Blum, Robert W. Floyd, Vaughan Ronald Pratt, Ronald L. Rivest, and
Robert Endre Tarjan. Time bounds for selection. Journal of Computer and System
Sciences, 7(4):448–461, 1973. 1

[BH85]

Béla Bollobás and Pavol Hell. Sorting and graphs. In Ivan Rival, editor, Graphs and
Order, volume 147 of NATO ASI Series, pages 169–184. Springer Netherlands, 1985.
1.1

[BM08]

Mark Braverman and Elchanan Mossel. Noisy sorting without resampling. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA ’08, pages 268–276, Philadelphia, PA, USA, 2008. Society for Industrial and
Applied Mathematics. 1.1, 3.1, 2, 15

[BM09]

Mark Braverman and Elchanan Mossel. Sorting from noisy information. CoRR,
abs/0910.1191, 2009. 1.1

[BSC+ 13]

Róbert Busa-Fekete, Balázs Szörényi, Weiwei Cheng, Paul Weng, and Eyke
Hüllermeier. Top-k selection based on adaptive sampling of noisy preferences. In
Proceedings of the 30th International Conference on Machine Learning, ICML 2013,
Atlanta, GA, USA, 16-21 June 2013, pages 1094–1102, 2013. 1.1

[BT83]

Béla Bollobás and Andrew Thomason. Parallel sorting. Discrete Applied Mathematics,
6(1):1 – 11, 1983. 1.1

[CBCTH13] Xi Chen, Paul N. Bennett, Kevyn Collins-Thompson, and Eric Horvitz. Pairwise
ranking aggregation in a crowdsourced setting. In Proceedings of the Sixth ACM
13

International Conference on Web Search and Data Mining, WSDM ’13, pages 193–
202, New York, NY, USA, 2013. ACM. 1
[CN91]

Andrew Caplin and Barry Nalebuff. Aggregation and social choice: A mean voter
theorem. Econometrica, 59(1):1–23, 1991. 1

[Col88]

Richard Cole. Parallel merge sort. SIAM J. Comput., 17(4):770–785, 1988. 1.1

[CS15]

Yuxin Chen and Changho Suh. Spectral MLE: top-k rank aggregation from pairwise comparisons. In Proceedings of the 32nd International Conference on Machine
Learning, ICML 2015, Lille, France, 6-11 July 2015, pages 371–380, 2015. 1.1

[DKNS01]

Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th International Conference on World Wide
Web, WWW ’01, pages 613–622, New York, NY, USA, 2001. ACM. 1

[Eri13]

Brian Eriksson. Learning to top-k search using pairwise comparisons. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics,
AISTATS 2013, Scottsdale, AZ, USA, April 29 - May 1, 2013, pages 265–273, 2013.
1.1

[HH81]

Roland Häggkvist and Pavol Hell. Parallel sorting with constant time for comparisons.
SIAM J. Comput., 10(3):465–472, 1981. 1.1

[Hoa61]

Charles Antony Richard Hoare. Algorithm 65: Find. Communications of the ACM,
4(7):321–322, 1961. 1

[Lei84]

Frank Thomson Leighton. Tight bounds on the complexity of parallel sorting. In
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30
- May 2, 1984, Washington, DC, USA, pages 71–80, 1984. 1.1

[LM00]

Frank Thomson Leighton and Yuan Ma. Tight bounds on the size of fault-tolerant
merging and sorting networks with destructive faults. SIAM Journal on Computing,
29(1):258–273, 2000. 1.1

[MMV13]

Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Sorting
noisy data with partial information. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS ’13, pages 515–528, New York, NY,
USA, 2013. ACM. 1.1

[PHC+ 13]

Chris Piech, Jonathan Huang, Zhenghao Chen, Chuong Do, Andrew Ng, and Daphne
Koller. Tuned models of peer assessment in moocs. In Proceedings of the Sixth International Conference on Educational Data Mining, EDM ’13, 2013. 1

[Rei81]

Rüdiger Reischuk. A fast probabilistic parallel sorting algorithm. In 22nd Annual
Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30
October 1981, pages 212–219, 1981. 1, 1.1

[Val75]

Leslie G. Valiant. Parallelism in comparison problems. SIAM J. Comput., 4(3):348–
355, 1975. 1, 1.1
14

A

Technical Lemmas

Before beginning our proofs, we provide a few technical lemmas that will be used throughout,
related to geometric sums, biased random walks, etc.
We first show the following reductions to prove that k = n/2 is the most difficult choice of k in
Select and Partition. We also show the reductions between Select and Partition.
Lemma 1. The following relations hold:
• Suppose A can solve Select / Partition in the case of n elements for any n, but only for
k = n/2. Then A can be used to solve Select / Partition for any k, n with the same
success probability.
• Suppose A can solve Select on n elements. We can construct algorithm B based on A to
solve Partition of n elements with one more round and extra n comparisons in the noiseless
model, O(n log n/γ) in the erasure model, and O(n log n/γ 2 ) in the noisy model. The success
probability decreases by 1/poly(n) except in the noiseless model (where it doesn’t decrease).
• Suppose A can solve Partition of n + 1 elements . We can construct algorithm B based on
A to solve Select of n elements with the same number of round and twice the number of
comparisons. If the original success probability was p, the new success probability is at least
p2 .
Proof. Let’s show the reductions one by one:
• Wlog, let k < n/2. The algorithm to solve Select / Partition is the following:
1. Generate n − 2k dummy elements which are smaller than all the n elements.
2. Run A on n elements together with n − 2k dummy elements.
3. Output A’s output.
It’s easy to check the above algorithm works.
• B is the following:
1. Run A, let x be the median output.
2. In the next round, compare every element to x (once in the noiseless model, O(log n/γ)
times in the erasure model, and O(log n/γ 2 ) times in the noisy model). For each element,
if it beats x, accept it (in the noisy model, if at least half of the comparisons beat x).
Otherwise reject it.
It’s easy to check B works.
• B is the following:
1. Generate two dummy elements x1 and x2 . x1 is smaller than all of the n elements and
x2 is larger than all of the n elements.
2. Do the followings in parallel:
(a) Run A on n elements and x1 .
(b) Run A on n elements and x2 .
3. Output the element that is accepted in the first run and rejected in the second run.
It’s easy to see that B works.

15

Lemma 2. For a ∈ (0, 1],

P∞

−ai ik
i=0 e

≤ 2k!/ak+1 . For a ∈ [1, ∞),

P∞

−ai ik
i=0 e

≤ 2k!/ak

Proof. First, note that the function e−ax xk has derivative zero exactly once in (0, ∞), at x =
k/a. So the function is increasing on (0, k/a) and decreasing on (k/a, ∞). This means that
R
P⌊k/a⌋−1 −ai k R ⌊k/a⌋ −ax k
P
−ai ik ≤ ∞
−ax xk . Putting these together,
e i ≤ 0
e
x , and that ∞
i=0
⌊k/a⌋+1 e
⌊k/a⌋ e
we get:
∞
X

−ai k

e

i=0

Note that

(k/e)k

≤ k!, and

R∞
0

i ≤

Z

∞

e−ax xk dx + e−k (k/a)k

0

e−ax xk dx = k!/(ak+1 ), completing the proof.

Lemma 3. The distribution that is heads with probability 1/2 + δ and tails with probability 1/2 − δ
has 1 − Θ(δ2 ) bits of entropy.
Proof.

H(1/2 + δ)
= −((1/2 + δ) log2 (1/2 + δ) + (1/2 − δ) log 2 (1/2 − δ))

= 1 − (((1/2 + δ) log 2 (1 + 2δ) + (1/2 − δ) log2 (1 − 2δ))

= 1 − ln(2) · ((1/2 + δ)(2δ − (2δ)2 /2) + (1/2 − δ)(−2δ − (−2δ)2 /2) + o(δ2 ))

(Taylor Expansion)

2

= 1 − Θ(δ ).

Proposition 2. Consider a biased random walk that moves right with probability p ≤ 1/2 and left
with probability 1 − p at every step. Then the probability that this random walk reaches k units right
of the origin at any point in time is exactly (p/(1 − p))k .

Proof. First, note that the probability that this random walk reaches k units right of the origin at
any point in time is exactly the probability that a random walk with the same bias reaches 1 unit
right of the origin k times independently, because once the random walk reaches 1 unit right of
the origin, the remaining random walk acts like a fresh random walk that now only needs to move
k − 1 units to the right at some point in time. So we just need to show that the probability that
the random walk moves 1 unit to the right at some point in time is p/(1 − p).
Note that whatever this probability, q, is, it satisfies the equality q = p + (1 − p)q 2 . This
is because the probability that the random walk moves right is equal to the probability that the
random walk moves right on its first step, plus the probability that the random walk moves left
on its first step, and then moves two units right at some point in time. This equation has two
solutions, q = p/(1 − p) and q = 1. So now we just need to show that q 6= 1 when p < 1/2.
Assume for contradiction that q = 1. Then this means that the random walk not only reaches
one unit right of the origin once during the course of the random walk, but that it reaches one unit
right of the origin infinitely many times, as every time the walk reaches the origin is a fresh random
walk that moves one unit right with probability one. So let Aj denote the random variable that is 1
if the walk moves right at time j, and −1 if the
Pwalk moves left at time j. We have just
P argued that
if q = 1, there are infinitely many
P t such that j≤t Aj /t > 0. Therefore, lim inf t→∞ j≤t Aj /t ≥ 0.
Aj /t] = 1 − 2p < 0, and the Aj s are independent. So the law
However, we also know that E[ j≤t P
of large numbers states that limt→∞ j≤t Aj /t = 1 − 2p, a contradiction.
16

We also include a technical lemma confirming that it is okay to do all of our sampling without
replacement, if desired.
Lemma 4. Let S be anyP
set of n elements,
X1 , . . . , Xk be k samples from S without
P all in [0, 1]. Let−δ
2
replacement. Then P r[| i Xi − (k/n) s∈S s| ≥ δk] ≤ 2e k/2 .
P
Proof. Define Yj = E[ i Xi |X1 , . . . , XP
, j = 1, . . . , n form
j ]. It’s clear that the YjP
P a martingale
(specifically, the Doob martingale for i Xi ), and that Y0 = E[ i Xi ] = (k/n) j yj . So we just
need to reason about how much the conditional expectation can possibly change upon learning a
single Xi , then we can apply Azuma’s inequality.
Conditioned on X1 , . . . , Xj , each of the remaining n − j elements of S are equally likely to
Pj
be chosen, and each is chosen with probability exactly (k − j)/(n − j). So Yj =
i=1 Xi +
P
k−j
s.
How
much
can
|Y
−
Y
|
possibly
be?
We
have
(below,
unsampled
means
j
j−1
unsampled s∈S n−j
elements that are still unsampled even after step j):
Yj − Yj−1 =
=

n−k
Xj +
n−j

X

unsampled s∈S

(

k−j+1
k−j
−
)s
n−j
n−j +1

n−k
n−k
Xj −
n−j
(n − j)(n − j + 1)

X

s

unsampled s∈S

It is clear that the above quantity is at most 1, because all s ∈ [0, 1], and n−k
n−j ∈ [0, 1] as well.
P
n−k
≤ 1.
It is also clear that the above quantity is at least −1, as unsampled s∈S s ≤ n − j, and n−j+1
So the Doob martingale has differences at most 1 at each step, and a direct application of Azuma’s
inequality yields the desired bound.

B

Proofs for Non-Adaptive Algorithms

B.1

Upper Bounds

Algorithm 1 Non-adaptive procedure for querying dn comparisons
√
1: Select a skeleton set, S, of size n (without replacement).
2: Compare each element of S to each other element of S.
3: Compare each element not in S to d − 1 random elements of S.
B.1.1

Noiseless Model

Algorithm 2 Non-adaptive algorithm for the noiseless model
1: Run Algorithm 1. Let S denote the skeleton set selected, and x denote the median of S.
2: Denote by AS the subset of S that beat x. Denote by RS = S − AS .
3: For all i ∈ S, accept i iff i ∈ AS . Otherwise, reject.
4: For all i ∈
/ S, if i beats an element in AS , accept. If an element in RS beats i, reject. Otherwise,
make a random decision for i.

17

Proof of Theorem 1: We consider the error contributed by n/2 + i (which is the same as n/2 − i).
There are two events that might cause n/2 + i to be misplaced. First, maybe n/2 + i loses to
y for some y ∈ S, y < x. This is unlikely because this can only happen in the event that x is
a poor approximation to the median. Second, maybe n/2 + i is never compared to an element
y ∈ [x, n/2 + i]. This is also unlikely because the fraction of such elements should be about i/n.
We bound the probabilty of the former event first.
Lemma 5. Let Xi denote the fraction
of elements in S greater than n/2+i. Then Xi ≤ 1/2−i/n+ε
2√
with probability at least 1 − 2e−ε n/2 .
√
Proof. Xi is the average of n independent random variables, each denoting whether n/2 + i <
some y ∈ S. E[Xi ] = 1/2 − i/n. Applying Lemma 4 yields the lemma.
We call a skeleton set S is good if for i = 1, .., n/2, Xi ≤ 1/2 − i/n + ε. Now let’s fix the skeleton
set S and assume
S is good. From the above lemma, we know S is good with probability at least
2 √n/2
−ε
1−n·e
.
Lemma 6. If S is good, then the probability that n/2 + i is rejected is at most (1 − i/n + ε)d−1
(and at most 1 if i/n ≤ ε).
Proof. The elements that n/2 + i are compared to are chosen uniformly at random from S. At
least a 1/2 + i/n − ε fraction of them are less than n/2 + i, so an i/n − ε fraction of elements in
S lie in [x, n/2 + i]. So each time we choose a random element of S to compare to n/2 + i, we
have at least a max{i/n − ε, 0} chance of comparing to an element in [x, n/2 + i]. In the event that
this happens, we are guaranteed to accept n/2 + i. The probability that we miss on each of d − 1
independent trials is exactly (1 − i/n + ε)d−1 .
Therefore, conditioning that S is good, the expected c-weighted error contributed by elements
n/2 + 1, ..., n is at most :
n/2
X
i=1

min{1, (1 − i/n + ε)}d−1 ic ≤

εn
X
i=1

n/2

X

i=εn

ic +

n/2
X

(1 − i/n + ε)d−1 ic

i=εn

n/2

(1 − i/n + ε)d−1 ic ≤
dε

≤e

n/2
X

X

e(d−1)(−i/n+ε) ic

i=εn

e−(d−1)i/n ic

i=1

≤ 2edε c!(n/(d − 1))c+1
The last inequality is a corollary of Lemma 2 proved in Appendix A. Taking ε = 1/d shows
c+1
2nc+1 edε c!
that the expected c-weighted error contributed by elements n/2 + 1, ..., n is (nε)
c+1 + (d−1)c+1 =
O((n/d)c+1 ) conditioned on S is good. Notice that when S is fixed, the c-weighted error contributed
by each element is independent and bounded by nc . By the Hoeffding bound, the probability
3
2c+2
that the c-weighted error exceeds its expectation by more than (n/d)c+1 is at most e−2n /d
conditioned on S is good. To sum up, taking elements that are smaller than the median into
18

account, we know that with probability at least 1 − 2n · e−
error is O((n/d)c+1 ). ✷

√

n/(2d2 )

− 2e−2n

3 /d2c+2

, the c-weighted

Here we also show that our algorithm is better than a simpler solution. The simpler solution
would be to just compare every element to a random d elements, and accept if it is larger than
at least half, and reject otherwise. We show that, unlike the algorithm above, this doesn’t obtain
asymptotically optimal error as d grows.
Theorem 14. The simple solution has expected error Ω(nc+1 /d(c+1)/2 ).
Proof. Let Xij be an indicator variable forP
the event that n/2+i is smaller than the j th element it is
compared to. Then n/2+ i is accepted iff j Xij > d/2. As each Xij is a bernoulli random variable
that is 1 with probability 1/2− i/n, the probability that n/2+ i is mistakenly rejected is exactly the
probability that a B(d, 1/2 − i/n) random variable exceeds its expectation
by at least di/n. This
√
2d
−(i/n)
happens with probability on the order of e
. So for
√ i = O(n/ d), this is at least 1/e, meaning
that the error contribution from all n/2 + i, i ≤ kn/ d for some √absolute constant k is at least
Pkn/ d
ic /e. Summing over all i means that the total error is at least i=1 ic /e = Ω(nc+1 /d(c+1)/2 ).
B.1.2

Erasure Model

Algorithm 3 Non-adaptive algorithm for the erasure model
1: Run Algorithm 1. Let S denote the skeleton set selected.
2: Say that element a ∈ S is known to beat element b ∈ S if there exists some a = s0 > s1 > . . . >
sℓ = b with all sj ∈ S, and sj beats sj+1 for all j ∈ {0, . . . , ℓ − 1} (i.e. all of these comparisons
were not erased).
3: Denote by AS the elements of S that are known to beat at least |S|/2 elements of S. Denote
by RS the elements of S that are known to be beaten by at least |S|/2 elements of S (note that
S may not equal AS ∪ RS ).
4: For all i ∈ S, accept i if i ∈ AS . Reject i if i ∈ RS . Otherwise, make a random decision for i.
5: For all i ∈
/ S, if i beats an element in AS , accept. If an element in RS beats i, reject. Otherwise,
make a random decision for i.
Proof of Theorem 2: We again consider the error contributed by n/2 + i (which is the same as
n/2 − i). There are again two events that might cause n/2 + i to be misplaced. First, maybe it
is beaten an element in RS . This is unlikely because this can only happen in the event that some
element below the median makes it into AS . Second, maybe i is never compared to an element that
beats it in AS . This is also unlikely because the fraction of such elements should be about i/n. We
bound the probabilty of the former event first, making use of Lemma 5.
Again let Xi denote the fraction of elements in S that are smaller than n/2 + i, and define S
to be good if Xi ≤ 1/2 − i/n +√ε for all i ∈ [1, n/2]. Then Lemma 5 guarantees that S is good with
2
probability at least 1 − ne−ε n/2 . This time, in addition to S being good, we also need to make
sure that AS is large (which will happen as long as not too many comparisons are erased).
Lemma 7. Let x, y ∈ S such that x > y and |S ∩ (x, y)| = k. Then with probability at least
2
1 − e−kγ , x is known to beat y.

19

Proof. x is known to beat y if there is some z ∈ S ∩ (x, y) such that the comparisons between x
and z and y and z are both not erased. There are k such possible z, and all comparisons are erased
independently. So the probability that for all z, at least one of the comparisons to {x, y} were
2
erased is (1 − γ 2 )k ≤ e−kγ .
Corollary 2. For all ε ∈ (0, 1/2), with probability at least 1 − n2 e−εγ
least (1/2 − ε)|S| elements.

2 √n

, both AS and RS have at
2

√

Proof. By Lemma 7 and a union bound, with probability at least 1 − n2 e−εγ n , it is the case that
for all x, y ∈ S that have at least ε|S| elements between them, it is known whether x beats y or
vice versa. In the event that this happens, any element that is at least ε|S| elements away from
the median will be in AS or RS .
We’ll call a skeleton set S really good if it is good, and |AS | ≥ (1/2 − ε)|S|. Now let’s fix the
skeleton set S and assume S is really√ good. From the
above arguments, we know S is really good
2 n/2
2 √n
−ε
2
−εγ
with probability at least 1 − n · e
−n e
.
Next, observe that if Xi ≤ 1/2 − i/n + ε, and |AS | ≥ (1/2 − ε)|S|, then there are at least
(i/n − 2ε)|S| elements in AS less than n/2 + i. Therefore the probability that n/2 + i never beats
an element in AS is at most (1−(i/n−2ε)γ)d−1 (and at most 1 if i/n ≤ 2ε). So the total c-weighted
error that comes from these cases is at most min{1, (1 − (i/n − 2ε)γ)d−1 }ic .
Conditioning on S is really good, the expected c-weighted error is
n/2
X
i=1

d−1 c

min{1, (1 − (i/n − 2ε)γ)}
n/2
X

i=2εn

i ≤

2εn
X

≤

n/2
X

i +

i=1

(1 − (i/n − 2ε)γ)d−1 ic ≤
≤ e2dεγ

c

n/2
X

i=2εn
n/2
X

(1 − (i/n − 2ε)γ)d−1 ic

e(d−1)γ(−i/n+2ε) ic

i=2εn

e−(d−1)γi/n ic

i=1

e2dεγ c!nc+1
(γ(d − 1))c+1

Taking ε =1/(γd) shows that 
the expected c-weighted error contributed by elements n/2 +
(2ε)c+1
e2dεγ c!
c+1
1, ..., n is n
= O((n/(γd))c+1 ) conditioned on S is really good. Notice
c+1 + (γ(d−1))c+1
that when S is fixed, the c-weighted error contributed by each element is independent and bounded
by nc . By the Hoeffding bound, the probability that the c-weighted error exceeds its expectation
3
2c+2
, conditioned on S is really good. To sum up,
by more than (n/(γd))c+1 is at most e−2n /(γd)
taking elements √that are smaller than
into account, we know that with probability at
√ the median
2 2
3
2c+2
, the c-weighted error is O((n/(γd))c+1 ).
least 1 − 2n · e− n/(2γ d ) − 2n2 e−γ n/d − 2e−2n /(γd)
✷

20

Algorithm 4 Non-adaptive algorithm for the noisy model
1: Run Algorithm 1. Let S denote the skeleton set selected.
2: Run the Braverman-Mossel algorithm to recover the maximum likelihood ordering of elements
in S in time poly(n, 1/γ) [BM08]. Let x denote the median under this ordering, and denote by
y <S z that y comes before z in this ordering.
3: For all i ∈ S, accept i iff i >S x, otherwise reject.
4: For all i ∈
/ S, let bi1 <S . . . <S bic denote the elements >S x that i is compared to (note that
maybe c = 0), and ℓi1 >S . . . >S ℓif denote the elements <S x that i is compared to.
5: Let Xij = 1 iff i beats bij , and −1 otherwise. Let Yij = 1 iff i beats ℓij and −1 otherwise. Let
P
P
Bi = max{J| Jj=1 Xij ≥ 0} and Li = max{J| Jj=1 Yij ≤ 0}. If Bi > Li , accept i. If Bi < Li ,
reject. If Bi = Li , make a random decision.
B.1.3

Noisy Model

Proof of Theorem 3: Again we consider the probability of mistakenly accepting the element n/2 + i.
This can happen for the same reasons as in the previous sections: perhaps the elements selected
for S are not representative of the ground set, or n/2 + i is not compared to elements that separate
it from the median. Additionally, mistakes may now happen due to erroneous comparisons, even
when n/2 + i is compared to “the right” elements. We proceed now to bound the probability of
each bad event, beginning with the event that S is poorly sorted due to comparison errors.
Theorem 15. ([BM08]) For each element e ∈ S, let π(e) denote the true rank of e when S
is properly sorted (i.e. the best element in S has rank
 1), and let σ(e) denote the rank of e in
the maximum likelihood ordering after taking all |S|
pairwise comparisons. Then there is an
2
absolute constant K such that for all ε and for all e simultaneously, with probability at least 1 − 2ε,
√
|π(e)−σ(e)| ≤ Kγ −4 (log |S|−log ε). In particular, taking ε = 1/poly(n) and recalling that |S| = n
implies that with probability at least 1 − 2/poly(n), |π(e) − σ(e)| = O(log(n)/γ 4 ) = o(|S|).
Now, we want to combine this with Lemma 5 to claim that there are not only many elements
in S smaller than n/2 + i, but that these elements are sorted well enough in S √for this to be useful.
2
Recall that Lemma 5 states that for all ε, with probability at least 1 − e−ε n/2 , the fraction of
elements in S larger than n/2 + i is at most 1/2 − i/n + ε. Combining Lemma 5 with Theorem 15
yields the following:
Corollary 3. For all ε, with probability at least 1 − 2/poly(n) − e−ε
such that:
• |T | ≥ (i/n − ε − o(1))|S|.
• Every element in T is >S x.
• Every element in T is smaller than n/2 + i.
• Every element in T is <S y, for all y ∈ S ∩ (n/2 + i, n].

2 √n/2

, there is a set T ⊂ S

are at least (1/2 + i/n − ε)|S| elements in S smaller than n/2 + i (except
Proof. By Lemma 5, there
2 √n/2
−ε
with probability e
). Therefore, by Theorem 15, the maximum likelihood ordering cannot
place any element > n/2 + i in any rank below (1/2 + i/n − ε − o(1))|S| (except with probability
1/n2 . So simply define T to be the set of elements ranked between |S|/2 and (1/2+i/n−ε−o(1))|S|,
and T necessarily satisfies the desired properties (except with the stated probability).
21

From here, the idea is that Bn/2+i is likely to be large, as the elements in T form a large set
immediately above x such that n/2 + i should beat more than half the elements in whatever subset
of T it is compared to. Similarly, we expect Ln/2+i to be small, because n/2 + i shouldn’t lose to a
large set of elements below x. We first show that n/2 + i is likely to be compared to many elements
of T .
Lemma 8. Let T be any set of size δ|S| elements. Then with probability at least 1 − e−δ(d−1)/8 ,
n/2 + i is compared to at least δ(d − 1)/2 elements of T .
Proof. n/2 + i is compared to a total of d − 1 elements of S, chosen independently and uniformly
at random. So each comparison is to an element in T with probability δ, and the expected number
of elements in T that n/2 + i is compared to is therefore δ(d − 1). Let Aj be the indicator random
variable that is 1 if the j th comparison is to anPelement in T and 0 otherwise. Then the number of
elements in T that n/2 + i is compared to is j Aj and is the sum of independent {0, 1} random
P
variables. Therefore, the Chernoff bound states that P r[ j Aj ≤ δ(d − 1)/2] ≤ e−δ(d−1)/8 .
Lemma 9. Let T ⊆ S be any set of elements such that:
• Every element in T is >S x.
• Every element in T is smaller than n/2 + i.
• Every element in T is <S y, for all y ∈ S ∩ (n/2 + i, n].
2
Then if n/2 + i is compared to at least t elements of T , P r[Bn/2+i ≥ t] ≥ 1 − e−tγ /8 .

Proof. Let T ′ denote the subset of T that n/2 + i is compared to. Define Aj to be a random
variable that is 1 if n/2 + i beats the j th element of T ′ , and 0 otherwise. Then Bn/2+i ≥ |T ′ | if
P|T ′ |
′
j=1 Aj ≥ |T |/2. As the Aj s are independent {0, 1} random variables that are 1 with probability

1/2 + γ/2, the Chernoff bound states that this probability is at least 1 − e−|T

′ |γ 2 /8

.

Finally, we show that Ln/2+i is likely to be small, and put everything together. Recall that
ℓ1 , . . . , ℓc denote the elements that n/2 + i are compared to that are <S x in decreasing order, and
that Yij = 1 iff n/2 + i beats ℓj , and −1 otherwise.
P
Lemma 10. Assume that every element <S x is also < n/2 + i. Then for all t, P r[ j≤t Yij ≥
tγ/2] ≥ 1 − e−tγ

2 /32

.

P
Proof. The random variables (1 + Yij )/2 are independent and in {0, 1}. E[ j≤t Yij ] = (1/2 + γ/2)t.
P
2
So the Chernoff bound states thatPP r[ j≤t (1 + Yij )/2 ≤ (1/2 + γ/4)t] ≤ e−tγ /32 . Note that
P
j≤t (1 + Yij )/2 ≤ (1/2 + γ/4)t ⇔
j≤t Yij ≤ tγ/2.

Proposition 3. Assume that every element <S x is also < n/2 + i. Then for all t, P r[Ln/2+i ≥
2
2
t] ≤ e−tγ /32 + e−tγ /2 .

Proof. Define a random walk starting at 0 that moves left at time j if Yij = −1, and right at time
j if Yij = 1. Then the event that Ln/2+i ≥ t is exactly
P the event that this random walk returns to
the origin (or left of the origin) at some step ≥ t. If j≤t Yij ≥ tγ/2, then this is exactly the event
that the random walk starting at time t winds up tγ/2 steps to the left. Note that this random
walk moves right with probability 1/2 + γ/2 and left with probability 1/2 − γ/2, so the probability
tγ/2 by Proposition 2.
that this event occurs is exactly ( 1/2−γ/2
1/2+γ/2 )
22

Finally, we observe:


1/2 − γ/2
1/2 + γ/2

tγ/2

≤ (1 − γ)tγ/2 ≤ e−tγ

2 /2

Now, we are ready to put everything
√ together to prove the theorem. By Corollary 3, with
2
probability at least 1 − 2/poly(n) − e−ε n/2 , there is a set of size (i/n − ε − o(1))|S| of elements immediately >S x that are all < n/2+i. By Lemmas 8 and 9, in the event that this happens, Bn/2+i ≥
2
(d − 1)(i/n − ε − o(1))/2 with probability at least 1 − e−(i/n−ε−o(1))(d−1)/8 − e−(i/n−ε−o(1))(d−1)γ /2 .
Furthermore, by Proposition 3, in the event that this happens, Ln/2+i < (d − 1)(i/n − ε − o(1))/2
2
2
with probability at least 1 − e−(i/n−ε−o(1))(d−1)γ /64 − e−(i/n−ε−o(1))(d−1)γ /4 .
Combining all of this with a union
bound, we see that n/2 + i is mistakenly accepted with
2
2√
probability at most 2/poly(n) + e−ε n/2 + 4e−(i/n−ε)(d−1)γ /64 . Taking ε = 1/d and summing this
over all i, we get:
n/2
X

(2/poly(n) + e−

√

n/2d2

)ic = o(nc+1 ).

i=1

n/2 

X
2
4e−(i/n−ε)(d−1)γ /64 ic
i=1

γ 2 /64

≤ 4e

n/2
X

e−((d−1)γ

2 /64n)i

ic

i=1

≤ 8c! 64nd−1 γ −2

c+1

.

The last inequality is due to Lemma 2. Summing both terms together yields the theorem.
✷

B.2

Lower Bounds

In the three subsections below, we provide proofs of the three lower bounds contained in Theorem 4.
B.2.1

Noiseless Model

The main idea of the proof is that if two elements i < n/2 and j > n/2 are never compared to any
elements in [i, j], then the results of these comparisons are independent of whether or not i and j
are swapped. So however the algorithm decides to place i and j, a coupling argument (by swapping
the role of i and j in all comparisons) shows that the error must be large if i and j are unlikely
to be compared to elements in [i, j]. We proceed by analyzing pairs of elements each a distance i
away from n/2 separately.
Let D be any distribution over set of comparisons chosen non-adaptively for the algorithm. As
the elements are a priori indistinguishable, it’s clear that D is invariant under permutations. So
let S denote a sample from D, and Si denote the same set after swapping the roles of n/2 − i and
n/2 + i in all comparisons. Let also Xi (S) denote the random variable that equal to the number
of {n/2 + i, n/2 − i} that are incorrectly classified by the algorithm with comparisons S. Then
23

P Pn/2
clearly the expected error is equal to S i=1 P r[S]E[Xi (S)]ic . And because D is invariant under
permutations, we can rewrite this as:
n/2
XX
S

P r[S]

i=1

E[Xi (S)] + E[Xi (Si )] c
i
2

Now we proceed to bound E[Xi (S)] + E[Xi (Si )].
Lemma 11. Let pi denote the probability that neither of {n/2 + i, n/2 − i} are compared to an eleP
i (Si )]
≥
ment in [n/2−i, n/2+i] when sampling a set of comparisons from D. Then S E[Xi (S)]+E[X
2
pi .
Proof. Because neither element is compared to an element between them, the result of all comparisons will be the same using S or Si . So coupling the randomness used by any algorithm with S
versus Si , we see that swapping the elements n/2 + i, n/2 − i simply swaps the set that each element
winds up in. If both are placed in R using S, then both are placed in R using Si , so each produces
one mistake. If both are placed in A using S, then both are placed in A using Si , so each produces
one mistake. If one is placed in A and the other in R using S, then the same holds using Si , but
swapped. So either S produces zero mistakes and Si produces two, or vice versa. So no matter the
algorithm, it is clear that when S does not contain comparisons between {n/2 + i, n/2 − i} and any
elements between them, that E[Xi (S)] + E[Xi (Si )] = 2.
Corollary 4. Let pi denote the probability that neither of {n/2 + i, n/2 − i} are compared to an
Pn/2
element in [n/2 − i, n/2 + i] during algorithm A. Then the expected error of A is at least i=1 pi ic .
The remaining work is to lower bound pi and evaluate the sum.

Lemma 12. For any algorithm A that makes at most dn non-adaptive queries, pi ≥ max{1 −
8di/n, 0}.
Proof. Because D is invariant under permutations, we can sample S by first building a graph with
n nodes and edges between two nodes that are compared, then randomly labeling the nodes with
1, . . . , n. For any pair (x, y), the probability that they are compared is then the probability that
two randomly selected nodes have an edge between them. If there are dn total edges in the graph,
this probability is (almost) exactly 2d/n. Taking a union bound over the 4i possible comparisons
means that the probability that either n/2 − i or n/2 + i is compared to something in between is
at most 8di/n.
Now, we may complete the proof by evaluating the sum.
n/2
X
i=1

n/8d
c

pi i ≥

X

pi ic

i=1

n/8d

≥

X
i=1

(1 − 8di/n)ic

n/8d

≥

X
i=1

c

i −

n/8d

X
i=1

24

8dic+1 /n

≥ (n/8d)c+1 /(c + 1) − 8d(n/8d)c+2 /n(c + 2)
= (n/8d)c+1 /(c + 1)(c + 2) = Ω((n/d)c+1 )

.
B.2.2

Erasure Model

We again consider swapping the role of n/2 + i and n/2 − i in all comparisons. This time, we
also have to couple whether or not each comparison is erased in addition to which comparisons are
made. Recall that each comparison is erased with probability 1 − γ and correct with probability γ.
Now, instead of just sampling which elements are compared, also sample whether the comparison
will be correct or erased.
It is clear that any erased comparison will give the same output whether the comparison is
made to n/2 + i or n/2 − i, and any comparison (correct or erased) made from an element in
{n/2 − i, n/2 + i} to an element outside of [n/2 − i, n/2 + i] will also give the same output for either
comparison. So the probability that the outcome of any comparison is different for n/2+i and n/2−i
is exactly the probability that there is a correct comparison from an element in {n/2 − i, n/2 + i}
to an element in [n/2 − i, n/2 + i].
So again, there are 4i possible comparisons that compare n/2 − i or n/2 + i to an element
between them. For each comparison, there is probability γ that the comparison is correct, and
probability 2d/n that it is made. So the probabilty that any fixed comparison is made and correct
is 2γd/n. Taking a union bound over all 4i possible comparisons means that the probability that
none of these comparisons are made is at least 1 − 8γd/n. From here, we may take exactly the
same sum as in the noiseless case, multiplying the appropriate terms by γ, and obtain the theorem:
n/8dγ

Error ≥

X
i=1

n/8dγ

≥
c+1

≥ (n/8dγ)

X
i=1

(1 − 8dγi/n)ic

n/8dγ
c

i −

X

8dγic+1 /n

i=1

/(c + 1) − 8dγ(n/8dγ)c+2 /n(c + 2)

= (n/8dγ)c+1 /(c + 1)(c + 2) = Ω((n/(dγ))c+1 )

.
B.2.3

Noisy Model

We again consider the algorithms performance on the pair {n/2 + i, n/2 − i}, but this time we will
have to reason using information theory instead of first principles. We will describe a reduction that
shows that any algorithm that makes few errors on this pair necessarily learns a lot of information
about their relative locations, and that this can only happen if the algorithm makes many queries
between {n/2 + i, n/2 − i} and [n/2 − i, n/2 + i].
Consider the following problem, Which-is-Which:
Input: A random permutation of the elements [n]. All elements are labeled except for n/2 + i and
n/2 − i. The input may be accessed via comparisons between two elements (labeled or unlabeled),
25

these comparisons will be correct with probability γ, and random with probability 1 − γ.
Output: A label for each of the unlabeled elements from {n/2 + i, n/2 − i}.
Goal: Maximize the probability that the elements are labeled correctly.
Lemma 13. Any algorithm that answers Which-is-Which correctly with probability 1/2+δ learns
Θ(δ2 ) bits of information (in expectation).
Proof. A solver running such an algorithm for Which-is-Which begins with a prior distribution
that each label is equally likely, which has one bit of entropy. After running the algorithm, the
solver’s posterior distribution has entropy 1 − Θ(δ2 ), by Lemma 3, which is proved in Appendix A.
Therefore, the solver must have learned Θ(δ2 ) bits of information to update her prior to her posterior.
Lemma 14. Any algorithm that learns b bits of information in expectation necessarily makes
Ω(b/γ 2 ) comparisons between elements in {n/2 + i, n/2 − i} and [n/2 − i, n/2 + i] in expectation.
Proof. Each comparison involving two labeled elements provides no new information, as these
elements are already labeled. Any comparison between unlabeled elements (elements in {n/2 +
i, n/2 − i}) and elements in [1, n/2 − i] ∪ [n/2 + i, n] provides no new information, as the probability
that the comparison will land one way or the other is independent on which unlabeled element is
n/2 + i and which is n/2 − i. The only comparisons that provide any information are those that
compare an unlabeled element to an element in [n/2 − i, n/2 + i]. So these comparisons are the
only source of information, and each such comparison provides O(1/γ 2 ) bits of information, by
Lemma 3.
Corollary 5. Any algorithm that answers Which-is-Which correctly with probability 1/2 + δ
makes Ω(δ2 /γ 2 ) comparisons between elements in {n/2 + i, n/2 − i} and [n/2 − i, n/2 + i] in expectation.
Now, we want to show that any algorithm that correctly accepts n/2 − i and rejects n/2 + i
implies an algorithm that solves Which-is-Which with good probability while making the same
comparisons. This would then imply that the original algorithm made many comparisons between
elements in {n/2 + i, n/2 − i} as well.
Lemma 15. Let A denote an algorithm for Select that makes Xi mistakes in expectation on
the elements {n/2 + i, n/2 − i}. Then there is an algorithm A′ for Which-is-Which that makes
exactly the same comparisons as A and is correct with probability 1 − Xi /2.
Proof. We define A′ as follows. Run A on the input provided. If both of the unlabeled elements
are accepted, or both are rejected, output a random answer. If one is accepted and the other is
rejected, guess that the accepted element is n/2 − i. A′ will then be correct exactly half of the time
that A makes one mistake, all of the time that A makes zero mistakes, and none of the time that
A makes two mistakes. So A′ is wrong with probability exactly Xi /2.
Corollary 6. Any algorithm that makes Xi < 1 mistakes in expectation on elements in {n/2 +
i, n/2−i} makes Ω(((1−Xi )/γ)2 ) comparisons between elements in {n/2+i, n/2−i} in expectation.
Finally, we are ready to apply a similar approach to the previous lower bounds. Note that,
because the input elements are a priori indistinguishable, each of the n2 possible comparisons are
26

made with probability ≈ 2d/n. As there are 4i comparisons that compare elements in {n/2 +
i, n/2 − i} to elements in [n/2 − i, n/2 + i], the expected number of such comparisons is ≈ 8di/n.
Applying the contrapositive
of Corollary 6, we see that such an algorithm cannot possibly make
p
fewer than 1 − Kdiγ 2 /n mistakes in expectation, for some absolute constant K. Now, we can
take similar sums to the previous lower bounds to complete the proof.
n/Kdγ 2

Error ≥
n/Kdγ 2

≥

X
i=1

X
i=1

(1 −

n/Kdγ 2
c

i −

X p
i=1

p

Kdγ 2 i/n)ic

Kdγ 2 /n · i(2c+1)/2

≥ (n/Kdγ 2 )c+1 /(c + 1) − Kdγ 2 /n · 2(n/Kdγ 2 )(2c+3)/2 /(2c + 3)
c+1 


1
2
n
−
=
Kdγ 2
c + 1 2c + 3
 !

nc+1
n c+1
=
=Ω
(Kdγ 2 )c+1 (c + 1)(2c + 3)
dγ 2
p

.

C

Proofs for Adaptive Algorithms in Noiseless Model

C.1
C.1.1

Two Rounds
Upper Bound

Proof of Theorem 5: First of all, it’s easy to see that Algorithm 5 has 2 rounds and makes r · n
comparisons in the first round and n comparisons in the second round.
Let’s show step 12 and step 13 in Algorithm 5 are valid. Notice that in step 9, the algorithm
compares every element in Si with every element in Ti . Since Si′ is a subset of Si , the algorithm
knows the comparison results between every element in Si′ and every element in Ti . Therefore the
algorithm knows the ranking of each element of Ti in Si′ . Thus the algorithm can find ai and bi
according to the rankings of elements of Ti in Si′ . By the comparison results between elements in
Ti and elements in Si′ , the algorithm can also figure out Ai . Finally, by looking at the rankings of
ai and bi in Si′ , the algorithm knows the ranking of the (pi−1 · |Si′ |)-th element of Si′ in Ai .
We then prove the following several lemmas to show that x is a good approximation of the
median.
Lemma 16. For each i in 1, ..., r, with probability at least 1 − 2e−n

ε /2

, |Ai | ≤ n1−2i/(2r+1)+ε .

Proof. Let A′ be the set of elements ranked from max{(pi−1 ·|Si′ |)−n1−2i/(2r+1)+ε /2, 1} to (pi−1 ·|Si′ |)
in Si′ . A′ has size at most n1−2i/(2r+1)+ε /2. For each sample in Ti , the probability that it is in A′
1−2i/(2r+1)+ε
is n2n1−i/(2r+1) . So the probability that Ti ∩ A′ = ∅ is at most
(1 −

1−2i/(2r+1)+ε
ε
n1−2i/(2r+1)+ε ni/(2r+1)
− n 1−i/(2r+1) ·ni/(2r+1)
2n
)
≤
e
= e−n /2 .
1−i/(2r+1)
2n

27

Algorithm 5 Two-round algorithm for the noiseless model making rn queries in round one
1: Variables Si will denote the ith refined skeleton set. Initialize S0 = [n].
2: Variables Ti will denote the pivots for Si (smaller sets will have more pivots).
3: Variables ai , bi will denote two elements of Ti , and we’ll denote Ai = [ai−1 , bi−1 ] ∩ Si . Initialize
a0 = 1, b0 = n.
th element of A
4: Variables ki will be such that the kith element of Ai is very close to the ki−1
i−1 .
Initialize k0 = k1 = n/2.
5: for i = 1 to r do
6:
Let Si be n1−i/(2r+1) random samples from Si−1 (without repetition).
7:
Let Ti be ni/(2r+1) random samples from Si (without repetition).
8: end for
9: In round one, for all i, compare every element in Si to every element in Ti .
10: for i = 1 to r do
11:
Let ai be the largest element in Ti that beats at most ki elements of Ai . Let bi be the smallest
element of Ti that beats at least ki elements of Ai .
12:
Update Ai+1 = [ai , bi ]∩ Si+1 , and update ki+1 so that the (ki+1 |[ai , bi ]∩ Ai |/|Ai+1 |)th element
of [ai , bi ] ∩ Ai is exactly the kith element of Ai .
13: end for
14: Let x be an arbitrary element of [ar , br ].
15: In round two, compare every element j to x. If j beats x, accept. Otherwise, reject.
Similarly, let A′′ be the set of elements ranked from (pi−1 ·|Si′ |) to min{(pi−1 ·|Si′ |)+n1−2i/(2r+1)+ε /2, |Si′ |}
ε
to in Si′ . With probability at most e−n /2 , Ti ∩ A′′ = ∅. When Ti ∩ A′ 6= ∅ and Ti ∩ A′′ 6= ∅,
Ai can only contain elements that ranked between max{(pi−1 · |Si′ |) − n1−2i/(2r+1)+ε /2, 1} and
min{(pi−1 · |Si′ |) + n1−2i/(2r+1)+ε /2, |Si′ |} in Si′ . So it is clear that |Ai | ≤ n1−2i/(2r+1)+ε . By union
ε
bound, with probability at least 1 − 2e−n /2 , |Ai | ≤ n1−2i/(2r+1)+ε .
Lemma 17. For each i in 2, ..., r, with probability at least 1 − e−n
n2/(2r+1)+ε or |Si′ | ≥ (1 − 1/(2r))|Ai−1 |/(n1/(2r+1) ).

1/(2r+1)+ε /(8r 2 )

, either |Ai−1 | ≤

Proof. Let’s consider the case when |Ai−1 | ≥ n2/(2r+1)+ε . For each element in Si−1 , the probability
that it is in Ai−1 is |Ai−1 |/|Si−1 |. So E[|Si′ |] = (|Ai−1 |/|Si−1 |) · |Si | = |Ai−1 |/n1/(2r+1) . By Cher−

noff bound, the probability that |Si′ | < (1 − 1/(2r))|Ai−1 |/(n1/(2r+1) ) is at most e
1/(2r+1)+ε /(8r 2 )
e−n
.

|Ai−1 |
8r 2 n1/(2r+1)

≤

ε

Lemma 18. Let q = 1/(1 − 1/(2r)). For each i in 1, ..., r, with probability at least 1 − 2e−n /2 −
1/(2r+1)+ε /(8r 2 )
ε
e−n
− 2e−n /4 , the min{pi · |Ai | + 2r(q r+1−i − 1)n(r+1−i)/(2r+1)+ε , |Ai |}-th element of
Ai is at most the min{pi−1 · |Ai−1 | + 2r(q r−i+2 − 1)n(r+2−i)/(2r+1)+ε , |Ai−1 |}-th element of Ai−1 and
the max{pi · |Ai | − 2r(q r+1−i − 1)n(r+1−i)/(2r+1)+ε , 1}-th element of Ai is at least the max{pi−1 ·
|Ai−1 | − 2r(q r−i+2 − 1)n(r+2−i)/(2r+1)+ε , 1}-th element of Ai−1 .
Proof. First from how we choose Ai we know that the min{pi ·|Ai |+2r(q r−i+1 −1)n(r+1−i)/(2r+1)+ε , |Ai |}th element of Ai is at most the min{pi−1 · |Si′ | + 2r(q r−i+1 − 1)n(r+1−i)/(2r+1)+ε , |Si′ |}-th element
of Si′ . When pi−1 · |Ai−1 | + 2r(q r−i+2 − 1)n(r+2−i)/(2r+1)+ε ≥ |Ai−1 |, the lemma is trivial. So let’s
consider the case that pi−1 · |Ai−1 | + 2r(q r−i+2 − 1)n(r+2−i)/(2r+1)+ε < |Ai−1 |.
28

ε

By Lemma 16, Lemma 17 and Union bound, we know that with probability at least 1−2e−n /2 −
e
, we have |Ai−1 | ≤ n1−(2i−2)/(2r+1)+ε and also either |Ai−1 | ≤ n2/(2r+1)+ε or |Si′ | ≥
1/(2r+1)
|Ai−1 |/(qn
). If |Ai−1 | ≤ n2/(2r+1)+ε , we have 2r(q r−i+2 − 1)n(r+2−i)/(2r+1)+ε ≥ |Ai−1 |
and the lemma becomes trivial. So let’s consider the case when |Ai−1 | ≤ n1−(2i−2)/(2r+1)+ε and
|Si′ | ≥ |Ai−1 |/(qn1/(2r+1) ).
Let X denote the number of elements in Si′ that is at most the pi−1 · |Ai−1 | + 2r(q r−i+2 −
1)n(r+2−i)/(2r+1)+ε -th element of Ai−1 . Then we have
−n1/(2r+1)+ε /(8r 2 )

E[X] = (pi−1 · |Ai−1 | + 2r(q r−i+2 − 1)n(r+2−i)/(2r+1)+ε ) ·

|Si′ |
|Ai−1 |

≥ pi−1 · |Si′ | + 2r(q r−i+1 − 1)n(r+1−i)/(2r+1)+ε + n(r+1−i)/(2r+1)+ε .
By Chernoff bound,
P r[X ≤ pi−1 · |Si′ | + 2r(q r−i+1 − 1)n(r+1−i)/(2r+1)+ε ]

≤ exp(−(n(r+1−i)/(2r+1)+ε /|Ai−1 |)2 · |Si′ |/2)

≤ exp(−n2(r+1−i)/(2r+1)+2ε /(2 · (qn1/(2r+1) ) · n1−(2i−2)/(2r+1)+ε ))
= e−n

ε /4

So when |Ai−1 | ≤ n1−(2i−2)/(2r+1)+ε and |Si′ | ≥ |Ai−1 |/(qn1/(2r+1) ), with probability at least 1 −
ε
e−n /4 , the min{pi · |Ai | + 2r(q r+1−i − 1)n(r+1−i)/(2r+1)+ε , |Ai |}-th element of Ai is at most the
min{pi−1 · |Ai−1 | + 2r(q r−i+2 − 1)n(r+2−i)/(2r+1)+ε , |Ai−1 |}-th element of Ai−1 . We can use the
same argument to show that when |Ai−1 | ≤ n1−(2i−2)/(2r+1)+ε and |Si′ | ≥ |Ai−1 |/(qn1/(2r+1) ), with
ε
probability at least 1 − e−n /16 , the max{pi · |Ai | − 2r(q r+1−i − 1)n(r+1−i)/(2r+1)+ε , 1}-th element
of Ai is at least the max{pi−1 · |Ai−1 | − 2r(q r−i+2 − 1)n(r+2−i)/(2r+1)+ε , 1}-th element of Ai−1 .
ε

By applying Lemma 18 for r times, we know that with probability at least 1 − r(2e−n /2 −
1/(2r+1)+ε /(8r 2 )
ε
−n
e
− 2e−n /4 ), the min{pi · |Ar | + n1/(2r+1)+ε , |Ar |}-th element of Ar is at most the
n/2 + 2r(q r+1 − 1)n(r+1)/(2r+1)+ε -th element of A0 and the max{pi · |Ar | − n1/(2r+1)+ε , 1}-th element
of Ar is at least the n/2 − 2r(q r+1 − 1)n(r+1)/(2r+1)+ε -th element of A0 and |Ar | ≤ n1/(2r+1)+ε .
So we know x is between n/2 − 2r(q r+1 − 1)n(r+1)/(2r+1)+ε and n/2 + 2r(q r+1 − 1)n(r+1)/(2r+1)+ε .
Therefore the c-weighted error is at most (2r(q r+1 − 1)n(r+1)/(2r+1)+ε )c+1 ≤ (8rn(r+1)/(2r+1)+ε )c+1 .
✷
By taking r = log n and nε = 8 log3 n we get the following corollary of Theorem 5:
Corollary 7. There exists a 2-round algorithm which takes n log n queries in each round and has
number of mistakes at most 128n1/2 log4 n with probability 1 − O(log n/n2 ).
C.1.2

Lower Bound

Proof of Theorem 6: We are going to show the c-weighted lower bound of the algorithm on the
uniform distribution of orders. Therefore, it is sufficient to prove this theorem for deterministic
algorithms since we are considering the expected number of mistakes the algorithm made on the
uniform distribution of orders. So without the loss of generality, let’s assume the 2-round algorithm
is a deterministic algorithm.

29

Suppose the algorithm labels all the elements as 1, ..., n. Let their rankings be a1 , ..., an . Then
a1 , ..., an is a uniformly random permutation of 1, ..., n. For any instance of run of the 2-round
algorithm, we define several terms. Let S = {i|n/2 − n/(32d) ≤ ai ≤ n/2 + n/(32d)}. Let
s = |S| = n/(16d). Let e(S) be the number of comparisons in the first round whose elements are
both in S. Then we have
E[e(S)] = dn ·

n/(16d) n/(16d) − 1
·
< n/(256d).
n
n−1

By averaging argument, with probability at least 3/4, e(S) ≤ n/(64d). Let A be the set of elements
that are in S and have not been compared with any other elements in S in the first round of the
algorithm. Then we have |A| ≥ s − 2 · e(S). If e(S) ≤ n/(64d), we have |A| ≥ n/(32d) = s/2.
Let’s fix comparison results S. Then A is also fixed by S. Let’s focus on the case when |A| ≥ s/2.
Let A′ be an arbitrary subset of A of size s/2. Let i1 , ..., is/2 be elements in A′ . Fix the rankings
of elements in {1, ..., n} − A′ . It’s easy to see that ai1 , ..., ais/2 will be s/2 distinct random elements
from [n/2 − n/(32d), n/2 + n/(32d)]. Also, since we have fixed S and A′ and rankings of elements in
{1, ..., n}−A′ , the result seen by the algorithm after the first round is fixed. So comparisons made by
√
√
the algorithm in the second round is determined. Now let T = {i|n/2−t n/2 ≤ ai < n/2+t n/2}.
√
Here t will be determined later. Let B = A′ ∩ T . We have E[|B|] = |Ts | · |A′ | = t n/2. We are
going to prove the following claim which we will use to show that in expectation there’s constant
fraction of elements in B that are not compared with elements in T even after the second round.
Claim 1. Fix S, A′ and rankings of elements in {1, ..., n} − A′ . For each comparison (x, y) in the
2 3/2
second round, the probability that x ∈ T and y ∈ B is at most 256t√nd .
Proof. We prove this claim by considering two cases.
1. x ∈ A′ : In this case, we have both x and y are in B. The probability that this is true is
|T | |T | − 1|
|T |
256t2 d3/2
√
·
≤ ( )2 = 256t2 d2 /n ≤
.
s
s−1
s
n
2. x ∈ S − A′ : In this case, we need the following lemma:
Lemma 19. If we pick s/2 random distinct elements from a set S of s elements. Then the
√
√
k-th element of these s/2 elements
is ranked between s/2 − t n/2 and s/2 + t n/2 among S
√
with probability at most 4t√sn .
√
Proof. The probability that k-th element of these s/2 elements is ranked between s/2−t n/2
√
and s/2 + t n/2 among S is
√
 s−u 
u−1
s/2+t n/2
X
k−1 s/2−k
.
s 
√
u=s/2−t n/2

It is easy to see that

u−1 s−u 
k−1 s/2−k

≤

√
s/2+t n/2

X

√
u=s/2−t n/2

s/22
.
s/4

s/2

Therefore, we have

u−1 s−u 
k−1 s/2−k
s 
s/2

30

√
≤t n·

s/22
s/4
s  .
s/2

By Stirling approximation, we know that
√
t n·

s/22
s/4

s
s/2

√

2π ≤

n!
nn+1/2 e−n

≤ e. Then we have


p 4
s/2 s/2
√
(s/2)
√
4t n
≤t n· √ 5 · 
p 4 √ ≤ √s .
2π
(s/4)s/4 s/4 ss s
e4

Then we have
√
√
256t2 d3/2
4t n t n
√
=
P r[x ∈ T, y ∈ B] = P r[x ∈ T ] · P r[y ∈ B|x ∈ T ] ≤ √ ·
.
s
s
n

Since in the second round, we have dn comparisons, the expected number of comparisons
2 3/2
1
that is in the form (x ∈ T, y ∈ B) is at most dn · 256t√nd . By picking t = 2048d
5/2 , we have
√
256t√2 d3/2
dn ·
≤ t n/8 . Let C ⊆ B be the set of elements that have not been compared with other
n
√
√
elements in T . Then we have E[|C|] ≥ E[|B|] − 2 · (t n/8) ≥ t n/4.
Finally, let’s fix the rankings of elements in A′ − C. Suppose the elements in C are j1 , ..., j|C| ,
√
√
then aj1 , ..., aj|C| are |C| distinct random elements between n/2 − t n/2 and n/2 + t n/2. Also
when we fix the rankings of {1, ..., n} − C, the comparison results got by the algorithms in both
the first round and the second round are determined. So the output of the algorithm is determined
and therefore the algorithm has expected number of mistakes |C|/2.
To sum up, any 2-round algorithm (maybe randomized) which makes dn comparisons in each
round has expected number of mistakes at least
√
3
· (t n/4) · (1/2) = Ω(n1/2 /d5/2 ).
4
✷
To complete the proof for c > 0, we observe that the best case scenario, conditioned on making
√
Ω( n/d5/2 ) mistakes in expectation is that the algorithm is correct on every element outside of
√
√
[n/2 − Ω( n/d5/2 ), n/2 + Ω( n/d5/2 )], and incorrect on every element in this window. This is
because elements
outside this window contribute more to the c-weighted error than elements inside.
PΩ(√n/d5/2 ) c
√
i = Ω(( n/d5/2 )c+1 ) as desired.
We have i=1

C.2

Three Rounds

We first provide a simple observation that is useful in the analysis of both Algorithm 6 and
Algorithm 7.
Observation 1. Suppose we have an algorithm A on Partition of n + 2t elements and A makes
mistakes only on elements between n/2 and n/2 + 2t. If we want to solve Partition on n element,
we can add 2t dummy elements which we assume they are smaller than other elements and run A
on these n + 2t elements. By doing this, if A claims some element x is smaller than the median of
the n + 2t elements, then x is indeed smaller than the median of the original n elements.
31

Algorithm 6 Three-round algorithm for the noiseless model making O(n log8 n) queries
√
1: Define t = 256 n log4 n.
2: Simultaneously do the following two steps in two rounds:
3: Run Algorithm 5 on the given input with 2t additional dummy 0 elements and r = log n (i.e.
treat these dummy elements as smaller than any of the real elements, and compare them to
each other arbitrarily). Let A(1) denote the set that was accepted, and R(1) the set that was
rejected.
4: Run Algorithm 5 on the given input with 2t additional dummy n + 1 elements and r = log n
(i.e. treat these dummy elements as larger than any of the real elements, and compare them to
each other arbitrarily). Let A(2) denote the set that was accepted, and R(2) the set that was
rejected.
5: Accept all elements in A(2) . Reject all elements in R(1) . Let U = R(2) ∩ A(1) be the remaining
elements.
6: if |U | > 4t then
7:
Make random decisions for all elements in U .
8: else
9:
Compare every element in U to every other element in U . Let x denote the (n/2 − |R(2) |)th
element of U .
10:
Accept every element in U that beat x, and reject every element in U that x beat.
11: end if
Proof of Theorem 7: Let’s first check the number of comparisons made by Algorithm 6. In the
first two rounds, by Corollary 7, Algorithm 6 makes at most 4(n + 2t) log(n + 2t) = O(n log n)
comparisons. In the third round, since U has size at most 4t, Algorithm 6 makes at most (4t)2 =
O(n log8 n) comparisons.
Now let’s analyze the correctness of Algorithm 6. Implicitly from the proof of Theorem 5, we
know that with probability 1 − O(log n/n2 ), Algorithm 5 used in step 3 and step 4 makes mistakes
only for elements that are most t away from the median of those n + 2t elements. In this case,
by Observation 1, we know that all elements in R(1) are smaller than the median of the original n
elements and all elements in A(2) are larger than the median of the original n elements. Also we
have |R(1) |, |A(2) | ≥ (n + 2t)/2 − t − 2t = n/2 − 2t. So |U | ≤ 4t and Algorithm 6 will also output
correctly on elements in U . To sum up, with probability 1 − O(log n/n2 ), Algorithm 6 outputs a
partition with zero c-weighted error. ✷

C.3

Four Rounds

Proof of Theorem 8: First it’s easy to check that the number of comparisons made Algorithm 7 is
O(n).
Now let’s analyze the correctness of Algorithm 7. Notice that the first two rounds of Algorithm
7 are almost the same as the first two rounds of Algorithm 6, except the fact that they use different
version of Algorithm 5. So we can use the same argument as the argument in the proof of Theorem
ε
1/3+ε /8
ε
ε
7. Then we get with probability 1 − 4e−n /2 − 2e−n
− 4e−n /4 = 1 − e−Ω(n ) , all elements in
R(1) are smaller than the median of the original n elements, all elements in A(2) are larger than the
median of the original n elements and |U | ≤ 4t. We call this as “succeed in the first two rounds”.
Now let’s consider the third round and analyze the probability that |W | ≤ n1/3+3ε assuming
32

Algorithm 7 Four-round algorithm for the noiseless model making O(n) queries
Pick any ǫ ∈ [0, 1/18]. Define t = n2/3+ǫ .
2: Simultaneously do the following two steps in two rounds:
3: Run Algorithm 5 on the given input with 2t additional dummy 0 elements and r = 1 (i.e.
treat these dummy elements as smaller than any of the real elements, and compare them to
each other arbitrarily). Let A(1) denote the set that was accepted, and R(1) the set that was
rejected.
4: Run Algorithm 5 on the given input with 2t additional dummy n + 1 elements and r = 1 (i.e.
treat these dummy elements as larger than any of the real elements, and compare them to each
other arbitrarily). Let A(2) denote the set that was accepted, and R(2) the set that was rejected.
1:

5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

Accept all elements in A(2) . Reject all elements in R(1) . Let U = R(2) ∩ A(1) be the remaining
elements.
if |U | > 4t then
Make random decisions for all elements in U .
else
Pick a random set V ⊂ U with |V | = n/|U |.
In round three, compare every element of V with every element of U .
Let x be the largest element in V that beats at most n/2 − |R(2) | elements of U . Let y be
the smallest element in V that beats at least n/2 − |R(2) | elements of U .
Reject every element in U that is beaten by x. Accept every element in U that beats y.
Denote by W the remaining elements.
if |W | > n1/3+3ǫ then
Make random decisions for every element in W .
else
In round four, compare every element in W to every other element in W .
Let R∗ denote the set of elements that have already been rejected. Let z denote the
(n/2 − |R∗ |)th element of W .
Accept all elements of W that beat z, and reject all elements that are beaten by z.
end if
end if

we succeed in the first two rounds. Let u be the size of U . We know u ≤ 4t. If the followings two
conditions were satisfied, |W | ≤ n1/3+3ε .
1. There is an element in V which ranks between u/2 − n1/3+3ε /2 and u/2.
2. There is an element in V which ranks between u/2 and u/2 + n1/3+3ε /2.
The probability that each condition is not satisfied is at most
(1 −

n1/3+3ε /2
n1/3+3ε /2 v
ε
·v
u
≤ e−Ω(n ) .
) ≤ e−
u

ε

So with probability 1 − e−Ω(n ) , |W | ≤ n1/3+3ε . It’s easy to see that if we succeed in the first two
rounds and |W | ≤ n1/3+3ε , Algorithm 7 outputs a partition with zero c-weighted error. By Union
ε
bound, with probability 1 − e−Ω(n ) , Algorithm 7 outputs a partition with zero c-weighted error. ✷
33

D

Proofs for Adaptive Algorithms in Erasure and Noisy Models

D.1
D.1.1

Upper Bounds
Proposition 1

Proof of Proposition 1: Wlog, let’s consider the problem we want to solve is Partition. We can do
this because the constructions shown below do not depend on which problem we want to solve. Let
the algorithm which solves Partition in the noiseless model be A. We prove the three statements
in the proposition one by one.
• We construct algorithm B1 in the erasure model that simulates A in the following way: For
each comparison A makes, B1 continues to make the same comparison until the result is not
erased. Clearly B1 solves Partition whenever A solves Partition. And for each comparison
A makes, in expectation, B1 makes 1/γ comparisons. So in total B1 makes Q/γ comparisons
in expectation. And as B1 is very adaptive, B1 ’s expected round complexity is only bounded
by Q/γ.
• We construct another algorithm B2 in the erasure model that simulates A and preserves the
number of rounds: For each round of A, B2 also starts a round of making each comparison
A made in that round c2 · (log Q + log n)/γ times simultaneously. Here c2 is some constant.
By setting c2 large enough, it’s easy to see that with probability 1 − 1/poly(n), all the
comparisons A wants to make are not erased. In this case, B2 solves Partition whenever A
solves Partition. By Union bound, B2 solves Partition with probability p − 1/poly(n).
• We construct another algorithm B3 in the noisy model that simulates A and preserves the
number of rounds: For each round of A, B3 also starts a round of making each comparison A
made in that round c3 · (log Q + log n)/γ 2 times simultaneously and returns to A the majority.
Here c3 is some constant. By setting c3 large enough, by Chernoff bound and union bound,
it’s easy to see that with probability 1 − 1/poly(n), A gets all the comparison results correct.
In this case, B3 solves Partition whenever A solves Partition. By Union bound, B3 solves
Partition with probability p − 1/poly(n).
✷
D.1.2

Multi-round Algorithm in Erasure Model

Algorithm 8 Algorithm comparing every element in [n] to pivot x (subroutine of Algorithm 9)
1: Initialize T = [n]. T will denote the subset of [n] that hasn’t been successfully compared to x
yet.
2: for i = 1 to log∗ (n) do
times.
3:
Compare each element of T to x 2i2n
|T |γ
4:
For each j, if any comparisons between j and x were not erased, remove j from T .
5: end for
Proof of Theorem 9: First, it is clear that Algorithm 9 has log∗ (n) + 8 rounds. It is also easy to
check Algorithm 9 makes O(n/γ) comparisons in total.
Similarly as the proof of Lemma 5, by using Lemma 4, with probability 1 − 1/poly(n), S1 ’s
median will be at most t elements away from the median of the n + 2t elements. Therefore S1 ’s
34

Algorithm 9 Algorithm for Partition in erasure model
1:
2:
3:

4:

5:
6:
7:
8:

Set t = n3/4 .
In rounds one thru four, simultaneously complete the following two steps.
Pick a random subset S1 of size n/ log n from n elements and 2t additional dummy 0 elements.
Run the 4-round algorithm guaranteed by Corollary 1 for Select on S1 . Let x1 denote the
median output.
Pick a random subset S2 of size n/ log n from n elements and 2t additional dummy 0 elements.
Run the 4-round algorithm guaranteed by Corollary 1 for Select on S2 . let x2 denote the
median output.
In rounds five thru log∗ (n) + 4, run Algorithm 8 to compare every element in [n] to both x1
and x2 .
Reject all elements that are beaten by x1 , and accept all elements that beat x2 . Let U denote
the set of elements that are not answered.
Add some dummy elements to U to make U ’s median be n/2. We can do this since we know
the rank of n/2 in U from the previous step. If |U | > 12t, fail.
In rounds log∗ (n) + 5 thru log∗ (n) + 8, Run the 4-round algorithm guaranteed by Corollary 1
for Partition on U . Reject and accept elements in U as the output of the 4-round algorithm.

median will be ranked between n/2−2t and n/2. Also by Corollary 1, we know that with probability
1 − 1/poly(n), x1 = the median of S1 . So by Union bound, with probability 1 − 1/poly(n), x1
is between n/2 − 2t and n/2. Similarly, with probability 1 − 1/poly(n), x2 is between n/2 and
n/2 + 2t.
We prove the following lemma to show that after running Algorithm 8, most elements have
non-erased comparison results with x1 and x2 :
Lemma 20. With probability 1 − 1/poly(n), |T | ≤ t at the end of Algorithm 8.
Proof. Let’s prove the following claim
n
th iteration, then with probability 1 − e−Ω(t) ,
Claim 2. If |T | ≤ max( (2↑↑(i−1))·2
i−1 , t) before the i

n
th iteration. Here ↑↑ is the notation for power tower, the inverse
|T | ≤ max( (2↑↑i)·2
i , t) after the i
∗
of log .

Proof. First if |T | ≤ t, the claim is trivial.
n
Now we assume t ≤ |T | ≤ (2↑↑(i−1))·2
i−1 before the i-th iteration. Now each element in T will

get 2↑↑(i−1)
comparisons with x. Then for each element in T , the probability that it stays in T
γ
after the i-th iteration is
(1 − γ)

2↑↑(i−1)
γ

≤ e−2↑↑(i−1) ≤

1
.
(2 ↑↑ i) · 2i+1

So the expectation of |T | after the i-th iteration is at most

probability 1

− e−Ω(t) ,

|T | ≤

n
.
(2↑↑i)·2i+1

By Chernoff bound, with

n
max( (2↑↑i)·2
i , t).

By using this claim inductively and Union bound, we know that with probability 1 − log∗ (n) ·
n
≥ 1 − 1/poly(n), |T | ≤ max( (2↑↑log ∗ (n))·2
log ∗ (n) , t) = t.

e−Ω(t)

35

By Lemma 20, we know that with probability 1 − 1/poly(n), there are at most 2t elements
that don’t have non-erased comparison results with both x1 , x2 . Together with the fact that with
probability 1 − 1/poly(n), x1 is between n/2 − 2t and n/2, x2 is between n/2 and n/2 + 2t, we
know that with probability 1 − 1/poly(n), |U | will be at most 6t before adding dummy elements
and at most 12t after adding dummy elements. In this case, it’s easy to see that Algorithm 8 solves
Partition correctly. ✷
D.1.3

Multi-Round algorithm for findMin in noisy model

Algorithm 10 Adaptive algorithm for findMin in the noisy model
1: Pick a random set S of size n/ log n. Find the minimum of S as x. (By Proposition 1, there’s
an algorithm with γn2 comparisons to find minimum with probability 1 − 1/n.)
2: Let U be the set of all elements. Run the following loop, and fail whenever more than 2cn
γ2
comparisons are used.
3: for k = 1 to log log n do
4:
Compare all elements in U to x for γc2 times.
ck
Remove any element y ∈ U that beats x for more than 2γ
2 times in total.
6: end for
7: If |U | > n/ log n, fail. Otherwise, find the minimum of U and output it. (We use the same
algorithm as step 1.)

5:

Proof of Theorem 12: Let’s consider the following events. It will be clear that if all of them happen,
then Algorithm 10 outputs the minimum. So we only have to show the probability that they all
happen is at least 1 − e−Ω(c) .
1. The first event is that we find the minimum of S correctly. This event happens with probability
at least 1 − 1/n.
√
2. The second event is that the minimum of S has rank ≤ n. This event happens with
√ n/ log n
probability 1 − (1 − 1/ n)
≥ 1 − 1/n
3. The third event is that for all k, after k-th iteration of step 2, |U | ≤ x’s rank + n · e−ck . By
Chernoff bound, the probability that an element that is larger than x stays in U after k-th
iteration is at most e−2ck . So by Markov inequality, the probability that after k-th iteration
|U | > x’s rank + n · e−ck is at most e−ck . By union bound, the third event happens with
P log n −ck
probability at least 1 − log
e
≥ 1 − 2e−c .
k=1
4. The fourth event is that the minimum is in U after step 2. Similarly as the argument for
the previous event, the probability that the minimum is not removed in theP
k-th iteration is
log n −2ck
1 − e−2ck . By union bound, the minimum is in U after step 2 is at least 1 − log
e
≥
k=1
−2c
1 − 2e .
5. The fifth event is that we find the minimum of U correctly if |U | ≤ n/ log n. This event
happens with probability at least 1 − 1/n.
√
When the second event and the third event both happen, we will spend at most γc2 ( n + n ·
Plog log n −ck
√
e ) ≤ 2nc
n + n · e−c log log n ≤ n/ log n.
k=1
γ 2 comparisons in step 2 and after step 2, |U | ≤
Then it’s clear if all these five events happen, the algorithm outputs the minimum correctly. And

36

by union bound, the probability that they all happen is at least 1 − 3/n − 2e−c − 2e−2c = 1 − e−Ω(c) .
✷

D.2
D.2.1

Lower Bounds
Lower Bound on findMin in Noisy Model

Proof of Theorem 13: We start with some notations used in the proof. Let’s call the algorithm
A. Let’s consider A’s successful probability on the uniform distribution of orders. Without loss of
generality, we can assume A is deterministic since if A is randomized, we can fix the randomness
which makes A achieves the highest successful probability. Assume A labels the n elements as
a1 , ..., an . Let S be the comparison results. S is just a γcn2 bits string. We use A(S) to denote
the output of the algorithm which is one of a1 , ..., an . Let g(i) denote the number of comparisons
involving element ai and an element that is smaller than ai , and the comparison result is correct.
Let b(i) denote the number of comparisons involving element ai and an element that is smaller
than ai , and the comparison result is wrong. Since A is deterministic, if we fix S, A(S) is fixed.
Let W denote the event that there are at least n/10 + 1 i’s such that g(i) − b(i) ≤ 9c
γ . Let π be a
permutation of a1 , ..., an . We use π to denote an ordering of a1 , ..., an in the following way: if ai
appears before aj in π, then it means ai < aj . Define π(k) be the k-th element in permutation π.
Let’s first show that W happens with some constant probability. We need two new terms p(i)
and q(i). They are set to be 0 before the algorithm’s run and we will show how they change during
the algorithm. For each comparison between ai and an element that is smaller than ai , let the
followings happen:
1. With probability γ, p(i) is increased by 1.
2. With probability (1 − γ)/2, q(i) is increased by 1.
3. With probability (1 − γ)/2, q(i) is decreased by 1.
It’s easy to check that (p(i) + q(i))’s have exactly the same distribution as (g(i) − b(i))’s. From the
rule above, we have
n
X
cn
p(i) =
E
γ
i=1

and

E

n
X

q(i)2 =

i=1

(1 − γ)cn
.
γ2

The second equation comes P
from the fact that ((x − 1)2 + (x + 1)2 )/2 = x2 + 1. So after each
n
2
comparison, in
Markov inequality, with probability
i=1 q(i) is increased by 1. By P
Pexpectation,
n
3cn
at least 2/3, i=1 p(i) ≤ γ . With probability at least 2/3, ni=1 q(i)2 ≤ 3cn
γ 2 . By union bound,
Pn
Pn
3cn
3cn
2
with probability at least 1/3, i=1 p(i) ≤ γ and i=1 q(i) ≤ γ 2 . In this case, at least n/2 i’s
9c
2
satisfy p(i) ≤ 6c
γ and at least 2n/3 i’s satisfy q(i) ≤ γ 2 . Then at least n/6 ≥ n/10 + 1 i’s satisfy
9c
2
both p(i) ≤ 6c
γ and q(i) ≤ γ 2 . Then for these i’s we have,
√
6c 3 c
9c
p(i) + q(i) ≤ p(i) + |q(i)| ≤
+
≤ .
γ
γ
γ
So with probability at least 1/3, there are at least n/10 + 1 i’s such that p(i) + q(i) ≤ 9c
γ . Since
(p(i) + q(i))’s have exactly the same distribution as (g(i) − b(i))’s, we have P r[W ] ≥ 1/3.
37

After showing P r[W ] ≥ 1/3, we are going to lower bound the probability that A outputs
incorrectly. For each permutation π, for each i such that ai 6= π(1), define π i = (ai , π(1), ..., π(k −
1), π(k + 1), ..., π(n)) assuming ai = π(k). There are two properties about π i :
1. Suppose we run A on ordering π and gets result S. Then g(i) and b(i) for all i are fixed.
Since π i only change the relative ordering between ai and the elements that are smaller than
ai , we have
P r[S|π]
(1/2 + γ)g(i) (1/2 − γ)b(i)
P r[S, π]
1/2 + γ g(i)−b(i)
=
=
)
.
=(
i
i
b(i)
g(i)
P r[S, π ]
P r[S|π ]
1/2 − γ
(1/2 + γ) (1/2 − γ)
2. For each ordering π ′ there are at most n π’s satisfy the condition that there exists an i such
that π i = π ′ .
By these two properties, we get the following:
X
X
P r[A outputs correctly] =
P r[π, S] ≤ P r[¬W ] +
P r[π, S]
π,S:π(1)=A(S)

10
≤ P r[¬W ] +
n

π,S:π(1)=A(S),W

X

P r[π, S]

X

P r[π i , S] · (

,i6=A(S),W
π,S,i:π(1)=A(S),g(i)−b(i)≤ 9c
γ

≤ P r[¬W ] +

10
n

≤ P r[¬W ] +

10
·
n

π,S,i:π(1)=A(S),g(i)−b(i)≤ 9c
,i6=A(S),W
γ

X

π,S:π(1)6=S

9c

n · P r[π, S] · e γ

1/2 + γ (g(i)−b(i))
)
1/2 − γ

·(8γ)
9c

= P r[¬W ] + 10 · P r[A outputs incorrectly] · e γ ·(8γ)

≤ 2/3 + 10e72c P r[A outputs incorrectly].
Therefore P r[A outputs incorrectly] ≥ e−72c /33. ✷

We provide the following lemma to show that Select is easier than Partition, even when
approximation is involved (we proved Lemma 1 only in the exact case). And then lower bounds of
Select also apply against Partition.
Lemma 21. Let c > 2 be some constant. In any of the three models, suppose there’s an algorithm A
on n elements that makes m comparisons and has at most t mistakes on Partition with probability
p. Then there’s an algorithm B on n − ct elements that obtains a ct/2-approximation for Select
with probability at least p2 · c−2
c+2 .
Proof. B has the following steps:
1. Let the n − ct elements be a1 , ..., an−ct .
2. Generate ct dummy elements b1 < · · · < bct which are smaller than any element in a1 , ..., an−ct .
Run A on a1 , ..., an−ct and b1 , ..., bct .
3. Generate ct dummy elements b′1 < · · · < b′ct which are larger than any element in a1 , ..., an−ct .
Run A on a1 , ..., an−ct and b′1 , ..., b′ct .
4. Let S ⊆ {a1 , ..., an−ct } be the of elements that are said to be above the median in the second
step and below the median in the third step. Output an random element in S.
38

Let S ′ be the elements that are at most ct/2 away from the median of {a1 , ..., an−ct }. If A does not
make any mistakes, it’s easy to check that S = S ′ . Now let’s consider the case that A has at most
t mistakes in both the second and the third step. The probability of this to happen is p2 . In this
case, we have |S ∩ S ′ | ≥ (c − 2)t and |S| ≤ (c + 2)t. It means in this case B outputs an element
c−2
that is ct/2 away from the median with probability at least (c−2)t
(c+2)t = c+2 . In total, B outputs an
c−2
.
element that is ct/2 away from the median with probability at least p2 · c+2
D.2.2

Lower Bound for Select in Erasure Model

Proof of Theorem 10: Let A be the algorithm we consider. Suppose A makes at most cn/γ
comparisons per round(c ≥ 1 is some constant.) and A has r = o(log∗ (n)) < log∗ (n)/(2C) rounds.
Here C = 28c . We will show that A fails to solve Select with probability at least 1/3.
Let’s prove the following claim by induction:
Claim 3. After round i, with probability 1 − i/n, there are at least
results are all erased. (↑↑ denotes the power tower.)

n
C↑↑i

elements whose comparison

Proof. Assume the claim is true for round i − 1. Let S be the set of elements whose comparison
results are all erased before round t. By induction hypothesis, with probability 1 − (i − 1)/n,
n
n
. In round i, by averaging argument, at least 2·(C↑↑(i−1))
elements in S have at most
|S| ≥ C↑↑(i−1)
2c·(C↑↑(i−1))
γ

comparisons in round i. For each such element s, the probability that s’s comparison
results are all erased in round i is at least
(1 − γ)

2c·(C↑↑(i−1))
γ

≥ 2−4c·(C↑↑(i−1)) .

Let S ′ be the set of elements whose comparison results are all erased after round i. Then we have
n
n
≥ 6c·(C↑↑(i−1)) .
2 · (C ↑↑ (i − 1))
2
√
n
≥ C↑↑r
≥ n. Then by Chernoff bound,

E[|S|] ≥ 2−4c·(C↑↑(i−1)) ·
It’s easy to check that

n
28c·(C↑↑(i−1))

≥

n
C↑↑i

P r[|S ′ | ≤

√

n

] ≤ e−Ω(
28c·(C↑↑(i−1))

n)

≤ 1/n.

By union bound, with probability 1 − (i − 1)/n − 1/n = 1 − i/n, there are at least
whose comparison results are all erased.

n
C↑↑i

elements

√
n
Now by this claim, we know that after round r, with probability 1−r/n, there are still C↑↑r
≥ n
elements whose comparison results are all erased. Let s be an element whose comparison results are
all erased. Even given all the relative orders of other elements except s, the rank of s is distributed
uniformly randomly in {1, ..., n}. So in this case any algorithm fails to output the median with
probability at least 1/2. To sum up, any r-round algorithm with O(n/γ) comparisons per round
fails to output the median with probability at least 12 · (1 − r/n) ≥ 1/3.
✷

39

D.2.3

Lower Bound on Rank in Noisy Model

First, we show that Rank is easier than Select in the noisy model. We will also formally define
Rank in the proof.
Proposition 4. In the noisy model, if there is an algorithm obtaining a t-approximation for Select on inputs of size 2n + 2t + 1 with probability p that has query complexity Q and round
complexity r, then there is an algorithm obtaining a t-approximation for Rank on inputs of size n
with probability p that has query complexity at most 2Q and round complexity r.
Proof of Proposition 4: Let A be the algorithm obtaining a t-approximation for Select on inputs
of size 2n + 2t + 1 with probability p that has query complexity Q and round complexity r. We
will first show algorithm B obtaining a t-approximation for Rank’ based on A. And then we will
show an algorithm C obtaining a t-approximation for Rank based on B. Rank’(n, t) is defined as
the following problem:
1. There are n elements a1 , ..., an , and another special element b. a1 , ..., an and b have some
underlying order unknown to the algorithm.
2. The goal is to output the number of elements in {a1 , ..., an } that are less than b with additive
error at most t.
3. The algorithm is allowed to make comparisons in the noisy model between pairs (ai , aj ) and
(ai , b).
The algorithm B to solve Rank’(n, t) by using A is the following:
1. Generate elements b1 , ..., bn+2t+1 .
2. Run A on elements a1 , ..., an , b1 , ..., bn+2t+1 .
3. Whenever A asks for a comparison:
(a) If the comparison is (bi , bj ), wlog let i < j, then return bj beats bi with probability
1/2 + γ and bi beats bj with probability 1/2 − γ.
(b) If the comparison is (ai , bj ), make a comparison (ai , b) and return the result to A.
(c) If the comparison is (ai , aj ), make a comparison (ai , aj ) and return the result to A.
4. If A’s output is some bi , output n + t + 1 − i.
5. If A’s output is some ai , fail.
We prove the following lemma to show that B works.
Lemma 22. B outputs the number of elements in {a1 , ..., an } that are less than b with additive
error at most t with probability at least p.
Proof. Suppose the underlying order of a1 , ..., an and b is ai1 < ai2 < · · · ais < b < ais+1 < · · · < ain .
Then it’s easy to see from B that A is running on the order ai1 < ai2 < · · · ais < b1 < · · · <
bn+2t+1 < ais+1 < · · · < ain . So the median of a1 , ..., an , b1 , ..., bn+2t+1 will be bn+t+1−s . And
the elements that are at most t elements away from median will be bn−s+1 , bn−s+2 , ..., bn−s+2t+1 .
Therefore, whenever A succeeds, B also succeeds. So B succeeds with probability at least p.
Next we are going to show an algorithm C obtaining a t-approximation for Rank based on B.
Let’s formally define Rank(n, t) as the following problem:
1. There are n elements a1 , ..., an , and another special element b. There’s an underlying order
for each pair (ai , b).
40

2. The goal is to output the number of elements in {a1 , ..., an } that are less than b with additive
error at most t.
3. The algorithm is allowed to make noisy comparisons in the form (ai , b).
The number of comparisons used in C will be at most twice the number of comparisons used in B.
The main idea of C is to create an underlying order of a1 , ..., an without knowing whether each ai
is less than b or not. Here is the algorithm C:
1. Run B on a1 , ..., an and b.
2. Whenever B asks a comparison:
(a) If the comparison is (ai , b), just make the same comparison and return the result to B.
(b) If the comparison is (ai , aj ), make two comparisons (ai , b) and (aj , b).
i. If ai beats b and b beats aj , then return ai beats aj to B.
ii. If b beats ai and aj beats b, then return aj beats ai to B.
iii. If b beats both ai and aj , then return ai beats aj if i > j to B. Otherwise return aj
beats ai to B.
iv. If b beats both ai and aj , then return ai beats aj if i < j to B. Otherwise return aj
beats ai to B.
3. Output B’s output.
We prove the following lemma to show that C works.
Lemma 23. C outputs the number of elements in {a1 , ..., an } that are less than b with additive
error at most t with probability at least p.
Proof. Here we only have to show that C feeds B with the noisy comparison results that are
consistent with some underlying order of a1 , ..., an and b, and this order is also consistent with the
underlying orders of all pairs (ai , b) in C’s input.
Let’s look at the comparison results fed to B. There are several cases. Work through these case
we will see what is the underlying order, and thus prove this lemma:
1. If the comparison is in the form (ai , b), definitely the above property is satisfied.
2. If the comparison is in the form (ai , aj ) and ai < b, aj < b, wlog let i < j, then the probability
that C returns ai beats aj to B is (1/2 − γ)2 + (1/2 + γ)(1/2 − γ) = 1/2 − γ. So for ai ’s that
are less than b, the order the same as the order of indices.
3. If the comparison is in the form (ai , aj ) and ai > b, aj > b, wlog let i < j, then the probability
that C returns ai beats aj to B is (1/2 + γ)2 + (1/2 + γ)(1/2 − γ) = 1/2 + γ. So for ai ’s that
are greater than b, the order the same as the reverse order of indices.
4. If the comparison is in the form (ai , aj ) and ai < b < aj , then the probability that C returns
ai beats aj to B is (1/2 + γ)2 + (1/2 + γ)(1/2 − γ) = 1/2 − γ. So if ai < b < aj , no matter
i < j or i > j, C always feeds B that ai beats aj with probability 1/2 − γ.
✷
Proof of Theorem 11: Let t = n3/8 /40. Suppose we have an algorithm C for Rank with o(n log n/γ 2 ) <
n log n
comparisons. We are going to show that C obtains a t-approximation for Rank with proba800γ 2
bility less than 2/3. Let’s consider C on the following input distribution: each ai is independently
41

chosen to be less than b with probability 1/2. Since we are considering the success probability of
C on a distribution, we can wlog assume C is deterministic.
Then we are going to use the technique similar to the technique in the proof of Theorem 13.
Let S be the comparison results. Let g(i) denote the number of correct comparisons between ai
and b. Let b(i) denote the number of wrong comparisons between ai and b. Let W be the event
n
that there are at least n/4 i’s such that |g(i) − b(i)| ≤ log
64γ . Notice W can be directly observed
from S. Similarly as the proof of Theorem 13, we need two new terms p(i) and q(i). They are set
to be 0 before the algorithm’s run and we will show how they change during the algorithm. For
each comparison between ai and b, let the followings happen:
1. With probability γ, p(i) is increased by 1.
2. With probability (1 − γ)/2, q(i) is increased by 1.
3. With probability (1 − γ)/2, q(i) is decreased by 1.
It’s easy to check that p(i) + q(i) has exactly the same distribution as g(i) − b(i). From the rule
above, we have
X
n log n
nmp(i) =
E
800γ
i=1

and

E

n
X
i=1

q(i)2 =

(1 − γ)n log n
.
800γ 2

P
log n
By Markov inequality, with probability at least 3/4, ni=1 p(i) ≤ n200γ
. With probability at least
P
Pn
log n
n log n
2
and
3/4, i=1 q(i) ≤ 200γ 2 . By union bound, with probability at least 1/2, ni=1 p(i) ≤ n200γ
Pn
log
n
n
log
n
2
i=1 q(i) ≤ 200γ 2 . In this case, at least n/2 i’s satisfy p(i) ≤ 100γ and at least 3n/4 i’s satisfy

q(i)2 ≤
have,

log n
.
50γ 2

Then at least n/4 i’s satisfy both p(i) ≤

log n
100γ

and q(i)2 ≤

log n
.
50γ 2

Then for these i’s we

√
log n
log n
log n
+√
≤
.
|p(i) + q(i)| ≤ p(i) + |q(i)| ≤
100γ
64γ
50 · γ

Now condition on some comparison results S such that W is true. Let X be the set of i’s such
n
that |g(i) − b(i)| ≤ log
64γ . Let <X̄ be some underlying order between each pair (ai , b), i 6∈ X. We
also condition on <X̄ , and we want to study the distribution of underlying orders between pairs
(ai , b), i ∈ X. One critical thing to notice here is that since each ai is only compared with b, even
condition on the comparison results S, whether ai < b is independent from whether aj < b. For
each i ∈ X, we have
n
log n
P r[ai < b|S]
1/2 + γ log
P r[ai < b|S, <X̄ ]
8γ· log n
=
≤(
) 64γ ≤ e 64γ ≤ 2 4 = n1/4 .
P r[ai > b|S, <X̄ ]
P r[ai > b|S]
1/2 − γ

Similarly, we also have
1
P r[ai < b|S, <X̄ ]
≥ 1/4 .
P r[ai > b|S, <X̄ ]
n
Put them together, we get
1
1
≤ P r[ai < b|S, <X̄ ] ≤ 1 − 1/4 .
1/4
2n
2n
42

Therefore P r[W ] ≥ 1/2.
Finally we are going to use the anti-concentration inequality to show that algorithm C succeeds
with probability at most 1/5 when W holds. Let ui = P r[ai < b|S, <X̄ ]. We have E[Xi ] = 0.
Let Xi = 1ai <b|S,<X̄ − ui . Let σi2 = E[Xi2 ] = (1 − ui )ui > 4n11/4 . Let ρi = E[|Xi |3 ]. Let O =
P
√PO 2 . Let Φ(x) be the
i∈X 1ai <b|S,<X̄ . Let F (x) be the cumulative distribution function of
i∈X

σi

cumulative distribution function of standard normal distribution. By Berry-Eseen inequality, we
have
X
1
m
ρi
· 1/4 )−1/2 · max((1 − ui )2 + u2i ) ≤ 4n−3/8 .
sup |F (x) − Φ(x)| ≤ (
σi2 )−1/2 · max 2 =≤ (
i∈X σi
i∈X
100 4n
x∈R
i∈X

Let C(S) be the output of the algorithm, we have
P
P
C(S) + t − i∈X ui
C(S) − t − i∈X ui
qP
qP
P r[C succeeds|S, <X̄ ] ≤ F (
) − F(
)
2
2
σ
σ
i∈X i
i∈X i
P
P
C(S) + t − i∈X ui
C(S) − t − i∈X ui
qP
qP
≤ Φ(
) − Φ(
) + 8n−3/8
2
2
i∈X σi
i∈X σi
≤ Φ( qP

t

2
i∈X σi

−t
) − Φ( qP

2
i∈X σi

) + 8n−3/8

≤ Φ(1/10) − Φ(−1/10) + 8n−3/8 < 1/5.

To sum up,
P r[C succeeds] ≤ P r[¬W ]+P r[C succeeds|W ] < P r[¬W ]+P r[W ]·(1/5) ≤ 1/2+(1−1/2)·(1/5) ≤ 2/3.
✷

43

