DecreaseKeys are Expensive for External Memory Priority Queues

arXiv:1611.00911v1 [cs.DS] 3 Nov 2016

Kasper Eenberg∗

Kasper Green Larsen∗

Huacheng Yu†

Abstract
One of the biggest open problems in external memory data structures is the priority queue
problem with DecreaseKey operations. If only Insert and ExtractMin operations need to be
supported, one can design a comparison-based priority queue performing O((N/B) lg M/B N )
I/Os over a sequence of N operations, where B is the disk block size in number of words and M
is the main memory size in number of words. This matches the lower bound for comparison-based
sorting and is hence optimal for comparison-based priority queues. However, if we also need to
support DecreaseKeys, the performance of the best known priority queue is only O((N/B) lg 2 N )
I/Os. The big open question is whether a degradation in performance really is necessary.
We answer this question affirmatively by proving a lower bound of Ω((N/B) lglg N B) I/Os for
processing a sequence of N intermixed Insert, ExtraxtMin and DecreaseKey operations. Our
lower bound is proved in the cell probe model and thus holds also for non-comparison-based
priority queues.

∗

MADALGO, Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, grant
DNRF84. Department of Computer Science, Aarhus University. {kse,larsen}@cs.au.dk. Larsen is also supported
by a Villum Young Investigator Grant and an AUFF Starting Grant.
†
Department of Computer Science, Stanford University. yuhch123@gmail.com. Supported by NSF CCF-1212372.

1

Introduction

The priority queue is one of the most fundamental data structures. Priority queues support maintaining a set S of keys with associated priorities. The three most commonly supported operations
on a priority queue are the following:
• Insert(k, p): Add the key k to S with associated priority p.
• ExtractMin: Remove and return the (key-priority)-pair (k, p) from S, such that p is minimal
amongst all priorities associated to keys in S. If multiple elements have the same smallest
priority, an arbitrary of these pairs may be returned.
• DecreaseKey(k, p): Given a (key,priority)-pair (k, p) such that there is already a pair (k, p′ )
present in S, change the priority associated with k to the minimum of p and p′ .
The classic solution to the problem is the binary heap [5] data structure, which supports all three
operation in O(lg N ) time, where N is the size of S. This data structure assumes only that priorities
can be compared and thus is optimal by reduction from comparison-based sorting. Another classic
solution is the Fibonacci heap [7] which supports the DecreaseKey in amortized O(1) time per
operation, Insert in worst case O(1) time and ExtractMin in O(lg N ) amortized time. A paper by
Brodal [2] shows how to make all these operations run in worst case time as well. If we assume
priorities and keys are integers bounded by a polynomial in N , we can get below the comparisonbased sorting lower bound. In fact, Thorup [15] showed that priority queues and integer sorting are
equivalent in this setting, and thus by using the currently fastest
√ integer sorting algorithms [9, 8],
one obtains a priority queue with either expected amortized O( lg lg N ) time for each operation,
or deterministic amortized O(lg lg N ) time per operation. One important thing to remark for
integer keys (or even just keys that can be stored in hash tables with O(1) expected amortized
time bounds), is that we can always support the DecreaseKey operation in the same time bound as
Insert and ExtractMin if we allow Las Vegas randomization and amortization in all three bounds.
For the interested reader, see the reduction in Section A. In addition to the equivalence to sorting,
Thorup [14] has also presented a deterministic priority queue for integer priorities which supports
constant time Insert and DecreaseKey, while supporting ExtractMin in O(lg lg N ) time.
External Memory Data Structures. In many applications, in particular in database systems,
the maintained data set S is too large to fit in the main memory of the machine. In such cases,
most of the data structure resides in slow secondary memory (disk). In this setting, classic models
of computation such as the word-RAM are very poor predictors of performance. This is because
random access to disk is several orders of magnitude slower than random access in RAM, and thus
memory accesses are far more expensive than CPU instructions. The external memory model of
Aggarwal and Vitter [1] was defined to make better predictions of actual performance of algorithms
when data resides on disk. In the external memory model, a machine is equipped with an infinitely
sized disk and a main memory that can hold only M elements. The disk is partitioned into blocks
that can store B elements each. A data structure in this model can only perform computation on
data in main memory. A data structure transfers data between external memory and main memory
in blocks of B elements. The transfer of a block is called an I/O. The query time and update time
of a data structure is measured only in the number of I/Os spend and thus computation on data
in main memory is free of charge. The motivation for moving blocks of B elements in one I/O, is
that reading or writing B consecutive locations on disk is essentially just as fast as a single random
access, even when B is in the order of a million elements. Thus the goal in external memory data
structures is to make sure that memory accesses are very local.
1

Note that in external memory, the cost of scanning N elements on disk is only O(N/B) I/Os
(and not O(N )). Another important bound is the sorting bound, which says that N comparable
keys can be sorted in O(Sort(N )) = O((N/B) lg M/B (N/M )) I/Os [1] and this is optimal. A
natural assumption is that N ≥ M 1+ε for some constant ε > 0, in which case the bound simplifies
to O((N/B) lgM/B N ). For readability of the bounds, we make this assumption in the remainder
of the paper. The relationship between M and B is such that we always require M ≥ 2B. This
ensures that the main memory can hold at least two blocks of data. In the literature, it is often
assumed that M ≥ B 2 , which is known as the tall-cache assumption.
Priority Queues in External Memory. The priority queue is also one of the most basic data
structures in the external memory model of computation. By taking the classic binary heap and
modifying it to an M/B-ary tree with buffers of M elements stored in each node [6], one can
support the Insert and ExtractMin operation in amortized O((1/B) lgM/B N ) I/Os per operation.
For comparison based priority queues, this bound is optimal by reduction from sorting. Now the
really interesting thing is that if we are also to support the DecreaseKey operation, the best known
priority queue, due to Kumar and Schwabe [11] has all three operations running in amortized
O((1/B) lg2 N ) I/Os per operation. This is in sharp contrast to classic models of computation
where one can always support DecreaseKey at no extra cost if allowed Las Vegas randomization
and amortization. Moreover, the classic Fibonacci heap even has the DecreaseKey running in O(1)
time.
In addition to priority queues being interesting in their own right, they also have immediate
implications for Single Source Shortest Paths (SSSP) in external memory. The original paper of
Kumar and Schwabe introduced their priority queue in order to obtain more efficient algorithms for
external memory SSSP. They show that solving SSSP on a graph G = (V, E) can be done in O(|V |)
I/Os plus O(|E|) Inserts, O(|E|) DecreaseKeys and O(|E|) ExtractMin operations on an external
memory priority queue. In their solution, it is crucial that the DecreaseKey operation has precisely
the interface we defined earlier (i.e. taking a key and a new priority as argument without knowing
the previous priority). Combined with their priority queue, their reduction gives the current fastest
external memory SSSP algorithm for dense graphs, running in O(|V | + (|E|/B) lg 2 N ) I/Os. Thus
faster priority queues with DecreaseKeys immediately yield faster external memory SSSP algorithms
for dense graphs (see reference below for the sparse graph case). The big open question, which has
remained open for at least the 20 years that have past since [11], is whether or not a degradation
in performance really is necessary if we want to support DecreaseKeys.
Our main result is an affirmative answer to this question:
Theorem 1. Any, possibly Las Vegas randomized, external memory priority queue supporting
Insert in expected amortized tI I/Os, ExtractMin in expected amortized tE I/Os and DecreaseKey
in expected amortized tD I/Os, must have max{tI , tE , tD } = Ω((1/B) lglg N B) when N ≥ M 4+ε .
The lower bound holds also for non-comparison-based priority queues.
When B ≥ N ε , this lower bound is Ω((1/B) lglg N N ), whereas under the tall-cache assumption
(M ≥ B 2 ), one can design priority queues with only Insert and ExtractMin with an amortized cost
of O(1/B) per operation when B ≥ N ε (since lgM/B N becomes O(1)). This is a lg N/ lg lg N factor
difference in performance! Note that when we are proving lower bounds for non-comparison-based
data structures, we assume keys and priorities are O(lg N )-bit integers and that a disk block holds
Bw bits, where w = Θ(lg n) is the word size. Similarly, we assume the main memory can hold
M w bits. Our lower bound thus rules out an O(|V | + Sort(|E|)) I/O SSSP algorithm directly from
a faster priority queue. Our lower bound also shows an interesting separation between internal
2

memory and external memory models by showing that Las Vegas randomization and amortization
is not enough to support DecreaseKeys at no extra cost in the external memory model.
Related Work. Recent work of Wei and Yi [17] proves an external memory analog of Thorup’s
result on equivalence between integer sorting and priority queues. More specifically, they show
that if sorting N integers can be done in O(S(N )) I/Os, then there is an external memory priority
queue supporting Insert and ExtractMin in amortized O(S(N )/N ) I/Os per operation, provided
∗
∗
that S(N ) = Ω(2lg N ) where lg∗ N is the iterated logarithm. If S(N ) = o(2lg N ), their reduction
gives a priority queue with Insert and ExtractMin in amortized O((S/N ) lg∗ N ) I/Os. Note that
we are dealing with integers and not just comparable keys and priorities, thus we have no sorting
lower bound and it might be the case that S(N ) = O(N/B). In fact, Wei and Yi mention that their
reduction might be useful for proving a lower bound for external memory sorting of integers via a
lower bound for priority queues. Unfortunately, their reduction does not give efficient DecreaseKeys,
and thus our result does not imply an integer sorting lower bound.
For the related dictionary problem, i.e. maintaining a set S of integers under membership
queries, a sequence of papers by Yi and Zhang [19], Verbin and Zhang [16] and finally Iacono and
Pǎtraşcu [10], established tight lower bounds in external memory. Note that all these bounds are
for maintaining integers and thus comparison based lower bounds do not apply. Moreover, the
upper bounds for maintaining integers are far better than the comparison-based lower bounds say
is possible for comparable keys and priorities, see [3].
We also mention that in some applications where one needs to perform DecreaseKey operations,
one might know the previous priority of the (key,priority)-pair being updated. In that case, one
can support all three operations in O((1/B) lgM/B N ) I/Os per operations using e.g. the reduction
to sorting due to Wei and Yi [17].
Finally, for the application to SSSP mentioned early, there are more efficient solutions for sparse
graphs. The best
p known algorithm for sparse graphs is due to Meyer and Zeh [12] and solves SSSP
in roughly O( |E||V |/B lg2 |V |) I/Os (plus some I/Os for computing an MST). For |E| > |V |B,
this is slower than the solution of Kumar and Schwabe.

2

Two-Phase Communication Complexity

As mentioned in the introduction, our lower bound for priority queues hold also for non-comparisonbased priority queues. More specifically, we think of the main memory as being able to store M
words of w = Θ(lg N ) bits each. Similarly, a block has a total of Bw = Θ(B lg N ) bits. We
assume disk blocks have integer addresses in [2w ]. Priority queues can now perform arbitrary
computations on the main memory free of charge and we only count the number of disk blocks read
and written to. This corresponds exactly to the cell probe model [18] with cell size Bw = Θ(B lg N )
bits, augmented with a main memory of M w = Θ(M lg N ) bits that is free to examine. To use
a terminology consistent with the literature on cell probe lower bounds, we henceforth refer to
reading or writing a disk block as a cell probe (a cell probe thus corresponds to an I/O).
Our lower bound for priority queues follows by a reduction from communication complexity.
Such an approach is not at all new in data structure lower bounds, see e.g. [13]. However for the
priority queue problem, the standard reductions yield communication games with solutions that
are too efficient to yield lower bounds for priority queues. We thus exploit that the protocols we
obtain have a very special structure. To explain this further, we first introduce the communication
game we reduce from and then discuss the known upper bounds that forces us to look at the special
structure of our protocols:
3

Consider a communication game in which two players Alice and Bob both receive a subset of a
universe [U ]. Letting x denote Alice’s set and y denote Bob’s, the goal for the two players is that
both players learn the intersection of the two sets x and y, while minimizing communication with
Alice. This is the set intersection problem in communication complexity. The special case of set
intersection in which the players only need to decide whether x ∩ y = ∅ is known as the set disjointness problem and is amongst the most fundamental and well-studied problems in communication
complexity. We assume the reader is familiar with basic terminology in communication complexity,
i.e. deterministic protocols, private and public coin randomized protocols etc.
The Las Vegas, or zero-error, randomized communication complexity of set intersection has
been shown to be O(N ) if Alice and Bob both receive sets of size N in a universe [U ], i.e. independent of U [4]. This is too weak to give any useful lower bound for priority queues - we really need
bounds higher than N . One could ask if using deterministic communication complexity would help,
as the deterministic case has higher communication lower bounds. Unfortunately, our reduction
from priority queues inherently yields Las Vegas randomized protocols even when then priority
queue is deterministic (we use Yao’s min-max principle). In addition to this issue, our application
to priority queues have Alice’s set somewhat smaller than Bob’s, i.e. we are considering an asymmetric communication game, see e.g. [13]. Sadly there are also too efficient upper bounds for the
asymmetric case to yield any lower bound for priority queues. What saves us is that our reduction
from set intersection to priority queues results in protocols of a very special form: First Bob speaks
a lot while Alice is almost silent. They then switch roles and Alice speaks a lot while Bob is almost
silent, i.e. protocols have two phases. They key property of external memory priority queues, which
makes one of the players almost silent, is that if the data structure probes k cells, then those cells
have kBw bits. Specifying the address of a cell is thus much cheaper than specifying its contents.
This shows up in the communication protocol where one player essentially sends a factor B less
bits than the other. It turns out that such restrictions on the communication protocol rules out
efficient solutions and we can in fact prove lower bounds that are higher than the known upper
bounds without this two phase restriction. We define Two-Phase protocols and their cost in the
following:
We say that a Las Vegas randomized communication protocol P is a Two-Phase protocol if for
every root-to-leaf path in the protocol tree, there is exactly one node which is marked the phasetransition node. We think of all communication before the phase-transition node as belonging to
phase one and all communication afterwards as belonging to phase two. We say that a Las Vegas
randomized Two-Phase protocol P has expected cost C(P, x, y) := (a1 , b1 , a2 , b2 ) on input (x, y) (x
is given to Alice and y to Bob) if: When running P on (x, y), the expected number of bits sent by
Alice in phase one is a1 , the expected number of bits sent by Bob in phase one is b1 , the expected
number of bits sent by Alice in phase two is a2 and the expected number of bits sent by Bob in phase
two is b2 . We use Ca1 (P, x, y) as short for the expected communication of Alice in phase one. We
define Cb1 (P, x, y), Ca2 (P, x, y) and Cb2 (P, x, y) similarly. If the inputs to Alice and Bob are drawn
from a distribution µ, we say that the cost of P under distribution µ is C(P, µ) := (a1 , b1 , a2 , b2 )
where a1 = E(X,Y )∼µ [Ca1 (P, X, Y )], b1 = E(X,Y )∼µ [Cb1 (P, X, Y )], a2 = E(X,Y )∼µ [Ca2 (P, X, Y )] and
b2 = E(X,Y )∼µ [Cb2 (P, X, Y )].
Having defined Two-Phase protocol and their costs, we face one more challenge: Not any hard
distribution for Two-Phase set intersection can be used in our reduction to priority queues. We
are thus forced to prove lower bounds for a product distribution over Alice’s and Bob’s sets. Let
SetIntU,k,l denote the set intersection communication problem with sets in a universe [U ], such that
Alice’s set has size k and Bob’s set has size l. We present the hard distribution in the following
and our main theorem lower bounding the communication complexity of set intersection under this
distribution:
4

SI
for SetIntU,k,l Alice’s input X is sampled from all
Hard distribution UU,k,l
of size k uniformly at random. Independently, Bob’s input Y is sampled from all
of size l uniformly at random. They must both learn X ∩ Y .

U
k  subsets
U
l subsets

of [U ]
of [U ]

Lemma 1. No Las Vegas Two-Phase protocol P for SetIntU,k,l can have
SI
) = (o(k), o(l), o(k lg r), o(k/r))
C(P, UU,k,l

for any r > 1, l ≫ k and U ≫ l.
Observe that the last bound (Alice’s communication in the second phase) is k lg r, even if Bob
sends up to o(l) bits in the first phase. If we did not have two phases, a lower bound saying that it
is not possible for Bob to send o(l) bits and Alice to send o(k lg r) bits is simply not true since for
any ε > 0, there is a protocol in which Alice sends k lg(1/ε) bits and Bob sends εl bits. Thus it is
absolutely crucial that we have two phases, in which Bob’s longest message is sent in the first phase
and Alice’s longest message is sent in the second. We defer the proof of Lemma 1 to Section 4.
In the next section, we give our reduction to priority queues from Two-Phase protocols and derive
our priority queue lower bound from Lemma 1.
For the observant reader, we make an interesting technical remark: The lower bound holds even
for r as large as k, even when U is just slightly larger than k and l. One could perhaps think
that in this case, Alice could just send her set to Bob in the second phase for O(k lg(U/k)) bits
(and this is the only communication), which would then contradict the lower bound of Ω(k lg r)
if lg r = ω(lg(U/k)). The crucial point is that such a protocol will not have Alice learn the
intersection, so Bob has to send the intersection back. The expected size of the intersection is
kℓ/U , so Bob’s message would have to be that long. But this is already Ω(k/r) unless U ≥ ℓr ≥ kr.
This contradicts lg r being ω(lg(U/k)).

3

Two-Phase Set Intersection to Priority Queues

Our goal is to prove a lower bound for external memory priority queues support Insert, ExtractMin
and DecreaseKey. We actually prove a slightly stronger lower bound. More specifically, we prove
lower bounds for priority queues that support Insert, ExtractMin and Delete. The Delete operation
takes as input a key, and must remove the corresponding (key,priority)-pair from the priority queue.
A priority queue supporting DecreaseKey rather than Delete can support Delete as follows: First
do a DecreaseKey, setting the priority of the deleted key to −∞ (or some small enough number).
Then do an ExtractMin. We thus focus on proving lower bounds for priority queues with Insert,
ExtractMin and Delete.
We let B denote the disk block size in number of words of w = Θ(lg N ) bits and let M denote
the main memory size in number of words. To keep the math simple, we prove the lower bound
only in the regime N ≥ M 4+ε for some constant ε > 0. Our goal is to prove
Theorem 2. Any Las Vegas randomized external memory priority queue with expected amortized
tI probes per Insert, expected amortized tD probes per Delete and expected amortized tE probes per
ExtractMin must have max{tI , tD , tE } = Ω((1/B) lg lg N B) when N ≥ M 4+ε .
By the arguments above, this theorem also implies Theorem 1. To prove the theorem, we start
by describing our hard input distribution. In our hard distribution, we can have Deletes being
executed for keys that have not been inserted in the data structure. For the remainder of our
proof, we simply assume that a Delete operation for a key that is not present, has no effect. We
5

show in Section 3.3 how we can modify the proof to avoid Deletes of keys not present in the data
structure. Note also that our proof in the following only needs N ≥ M 1+ε . Altering the hard
distribution such that we have no Deletes of already inserted keys needs the extra requirement
N ≥ M 4+ε as stated in the theorem.
Hard Distribution. Let β ≥ 2 be an integer parameter. For an integer height h ≥ 8 and
memory size M , such that N ≥ M 1+ε for some constant ε > 0, consider a (2 + β)-ary tree T having
sequences of updates at the leaves. We assume for convenience that h is some multiple of 4. Such
a tree T defines a sequence of updates by forming the concatenated sequence of the updates in the
leaves of T as encountered during a pre-order traversal of T .
The topology of T is defined recursively in the following way: Given a height parameter hv ,
with hr = h for the root node r, a node v ∈ T is defined as follows: If hv = 0, v is simply a leaf.
We call such a leaf a delete-leaf. Otherwise, v has 2 + β children c1 (v), c2 (v), . . . , c2+β (v), in that
order (from left to right). Children c1 (v) and c2+β (v) are leaves, whereas c2 (v), . . . , c1+β (v) are
recursively constructed each with height parameter hv − 1. We call c1 (v) an insert-leaf and c2+β (v)
an extract-min-leaf.
Having defined the topology of T , we add updates to the delete-leaves of T as follows: We
place M h Delete operations in each of the β h delete-leaves. The keys assigned to these Deletes
are chosen by picking a uniform random set of M hβ h keys from [(M hβ h )4 ] and assigning them in
uniform random order to the Delete operations.
For each internal node v ∈ T of height hv , we place M β hv Inserts in the insert-leaf c1 (v). These
Inserts all have the priority hv . Summed over all insert-leaves, we have a total of M hβ h Inserts.
We now assign keys to the Inserts by drawing a uniform random set of M hβ h keys from [(M hβ h )4 ]
and assigning these keys in uniform random order to the Inserts.
Finally, we need to populate the extract-min leaves. For an internal node v ∈ T of height hv , we
place M β hv ExtractMins in the extract-min leaf c2+β (v). These ExtractMins returns a sequence of
key-priority pairs (k1 , p1 ), . . . , (kM β hv , pM β hv ), where this sequence is completely determined from
previous operations in T . We now re-insert all these pairs (ki , pi ) for which pi 6= hv .
This completes the description of the hard distribution. We refer to it as distribution D(β, h, M ).
We first state a simple property of the distribution:
Property 1. Distribution D(β, h, M ) is over sequences of M hβ h Deletes, at most 2M hβ h Inserts
and M hβ h ExtractMins.
The much more interesting property of D(β, h, M ) is the following: Consider a node v in T and
define the set Yv consisting of all keys inserted in c1 (v). The keys in Yv are all inserted with a priority
of hv in c1 (v). Also let Xv denote the set of keys deleted in some delete-leaf in the subtrees rooted
at c2 (v), . . . , c1+β (v). Precisely those keys in Yv that are not deleted by the Deletes corresponding
to Xv , will still have priority hv just before processing c2+β (v). Moreover, all Inserts performed
in the insert-leaves of the subtrees rooted at v’s children are with lower priorities. But these are
all extracted in the corresponding extract-min leaves. Thus when reaching c2+β (v), the keys in
Yv that have not been deleted are the keys in the priority queue with lowest priority. Therefore,
the key-priority pairs being extracted by the ExtractMins in c2+β (v) uniquely determines Yv \ Xv .
Combined with Yv , we therefore also learn Yv ∩ Xv .
What this property suggests, is that the priority queue has to solve a set intersection problem
between Yv and Xv in order to correctly answer the ExtractMins in c2+β (v). But the keys in the
delete-leaves are involved in h such set intersection problems, and thus intuitively they will have
to be read h times. This suggests roughly the lower bound we aim for, namely that each delete
6

operation causes h/B I/Os. Of course this whole argument is complicated by the fact that if the
priority queues figures out what the priorities are for the keys deleted by Xv , then the priority
queue can ignore all elements in Xv that do not correspond to keys of priority hv when solving the
set intersection problem on Yv and Xv . We thus have to carefully argue that if the priority queue
is very fast, then intuitively it cannot learn these priorities. Another technical issue we need to
tackle, is that we have to consider set intersection between Yv and the set of Deletes in only one
child’s subtree. The formal details are given later.
We are now ready to set the stage for our reduction from the Two-Phase communication complexity of set intersection. The first step in the reduction is to find a suitable node v in T into
which to “embed” the set intersection communication problem. We show how we do this in the
following subsection.

3.1

Finding a Node for Embedding

In the following, we show that for any efficient Las Vegas randomized external memory priority
queue Q∗ , if we run an update sequence drawn from D(β, h, M ) on Q∗ , then there is a node v
in T , such that when Q∗ processes the updates in the subtree rooted v, there is only very few
memory cells that are being updated during the operations corresponding to c1 (v) and then read
again during the operations in the subtree rooted at one of the other children ck (v). The precise
details become apparent in the following.
Fixing Random Coins of Data Structures. Assume Q∗ is a Las Vegas randomized external
memory priority queue with main memory size M , block size B, word size w = Θ(lg N ), having
expected amortized tI probes per Insert, expected amortized tD probes per Delete and expected
amortized tE probes per ExtractMin. By Property 1, Q∗ processes an entire sequence of updates
drawn from D(β, h, M ) with an expected t ≤ 2M hβ h tI + M hβ h tD + M hβ h tE probes in total.
Defining N = 4M hβ h as the maximum total length of an update sequence drawn from D(β, h, M ),
we see that t = O((tI + tD + tE )N ). By fixing the random coins of Q∗ , we get a deterministic
external memory priority Q with main memory size M , block size B, word size w, using expected
t probes to process an update sequence drawn from D(β, h, M ). We thus prove lower bounds on t
for such deterministic priority queues Q.
Assigning Probes to Nodes. Let I ∼ D(β, h, M ) be a random sequence of updates drawn from
D(β, h, M ). We use T to denote the (2 + β)-ary tree corresponding to I. Given a deterministic
external memory priority queue Q, let tQ (I) be the total number of probes performed by Q when
processing I. Our goal is to lower bound E[tQ (I)]. To do this, consider processing I on Q. For each
probe Q performs, let ℓ be the leaf of T in which the currently processed update resides and let
a ∈ [2w ] be the address of the cell probed. If this is the first time the block of address a is probed,
we say the probe is associated to the leaf ℓ. Otherwise, let z be the leaf in which a was last probed.
We then associate the probe to the lowest common ancestor of z and ℓ. For a node v ∈ T , define
P(v) as the set of probes associated to v after processing the entire update sequence I.
Since probes are associated to only one node each, it follows by linearity of expectation that
there must exist a height h∗ ∈ {h/2, . . . , h} such that


X
E
|P(v)| = O(t/h).
v∈T :v is internal,hv =h∗

7

∗

Consider the β h−h internal nodes at depth h∗ in T . Define for each node v of depth h∗ the quantity
∗
C(v) which gives the number of probes performed by all O(β h M h) updates in the subtree rooted
at v.
By Markov’s inequality, linearity of expectation and a union bound, it follows that there is at
least one of these nodes v ∗ ∈ T with


t
.
E [|P(v ∗ )|] = O
hβ h−h∗
and at the same time

∗

E[C(v ∗ )] = O(t/β h−h ).
For a probe p ∈ P(v ∗ ), let i(p) and j(p), with i(p) < j(p), be the indices of the children ci(p) (v ∗ ) and
cj(p) (v ∗ ) such that the probe p took place in the subtree rooted at cj(p) (v ∗ ) and was to a cell last
probed in the subtree rooted at ci(p) (v ∗ ). We define for each child ck (v ∗ ) the sets of probes L(v ∗ , k)
and R(v ∗ , k), where L(v ∗ , k) contains all probes p ∈ P(v ∗ ) with i(p) = k and R(v ∗ , k) contains
all probes p ∈ P(v ∗ ) with j(p) = k. Since each probe p ∈ P(v ∗ ) is stored only in L(v ∗ , i(p)) and
R(v ∗ , j(p)), it follows that there must exist an index k∗ ∈ {2, . . . , β + 1} such that


t
∗ ∗
∗ ∗
.
E [|L(v , k )| + |R(v , k )|] = O
hβ h−h∗ +1
Using that t = O((tI + tD + tE )N ) = O(max{tI , tD , tE }M hβ h ), the following lemma summarizes
the findings above:
Lemma 2. If Q∗ is a Las Vegas randomized external memory priority queue with main memory
size M , block size B, word size w, expected amortized tI probes per Insert, expected amortized tD
probes per Delete and expected amortized tE probes per ExtractMin, then there exists a deterministic
external memory priority queue Q with main memory size M , block size B, word size w = Θ(lg N ),
such that for I ∼ D(β, h, M ), there is a node v ∈ T with hv ∈ {h/2, . . . , h} and a child index
k ∈ {2, . . . , β + 1} such that


E [|L(v, k)| + |R(v, k)|] = O max{tI , tD , tE }M β hv −1
and at the same time
E[C(v)] = O(max{tI , tD , tE }M hβ hv ).
The remaining part of the argument is to prove a lower bound on E [|L(v, h)| + |R(v, h)|] and
thereby a lower bound on max{tI , tD , tE }. We proceed in the following section to establish this
lower bound by a reduction from Two-Phase communication complexity.

3.2

Embedding the Communication Game

With Lemma 2 established, we are ready to show our reduction from Two-Phase communication
complexity. Let D ∗ be a Las Vegas randomized external memory priority queue as in Lemma 2.
Then by Lemma 2, there is a deterministic priority queue Q for which we can find a node v ∈ T
with hv ∈ {h/2, . . . , h} and a child index k ∈ {2, . . . , β + 1} such that


E [|L(v, k)| + |R(v, k)|] = O max{tI , tD , tE }M β hv −1
and
E[C(v)] = O(max{tI , tD , tE }M hβ hv ).
8

We will use this deterministic priority queue Q and node v to obtain a Two-Phase protocol for
the set intersection problem in which Alice receives a set X of size M hβ hv −1 and Bob a set Y of
SI
, i.e. the sets
size M β hv . Assume these sets are drawn from the distribution U(M
hβ h )4 ,M hβ hv −1 ,M β hv

are uniform random and independent of each other from the universe [(M hβ h )4 ] = [N 4 ]. Alice
and Bob will now form an update sequence to the priority queue such that the distribution of that
update sequence is exactly D(β, h, M ). Their high-level approach is as follows: Alice and Bob will
use randomness to populate all leaves of T up to (and including) reaching the node c2+β (v) in a
pre-order traversal of T . The updates in c1 (v) will be known only to Bob and will represent his set
Y . The updates in the delete-leaves of ck (v) will be known only to Alice and will represent her set
X. The updates in all other populated nodes will be known to both of them. We give the details
of how these nodes are populated in the following:
Populating T . First we focus on populating all delete-leaves in T encountered up to reaching
node c2+β (v) in a pre-order traversal of T , except those in the subtree ck (v). This is done as
follows: Let L ≤ M hβ h denote the number of Delete operations that we need to choose keys for.
From public randomness, Alice and Bob sample a uniform random set of L keys from [(M hβ h )4 ].
Alice privately checks whether the sampled set intersects X. If not, she sends a 1-bit to Bob. If
they do intersect, she first sends a 0-bit to Bob. She then privately samples a new set of L keys
that is uniform random amongst all sets disjoint from X and sends that set to Bob. From public
randomness, they assign the sampled keys to the Delete operations in a uniform random order.
Next, they populate all insert-leaves encountered up to c2+β (v) in a pre-order traversal of T ,
except c1 (v). Let K ≤ M hβ h denote the number of Insert operations they need to choose keys
for. From public randomness, they sample a uniform random set of K keys from [(M hβ h )4 ]. Bob
privately checks whether the sampled set intersects Y . If not, Bob sends a 1-bit to Alice. If they do
intersect, Bob sends a 0-bit to Alice. He then privately samples a new set of K keys that is uniform
random amongst all sets disjoint from Y and sends that set to Alice. From public randomness,
they assign the sampled keys to the Insert operations in a uniform random order.
Finally, Bob privately populates c1 (v) by assigning the keys in his set Y in a uniform random
order to the Insert operations in c1 (v). Alice privately populates the delete-leaves in the subtree
rooted at ck (v) by assigning the keys in her set X in a uniform random order to the Delete
operations.
Observe that by the rejection sampling, the distribution of the Insert and Delete operations in
the insert-leaves and delete-leaves of T correspond exactly to distribution D(β, h, M ) when X and Y
SI
. Also observe that after having chosen these, the operations
are drawn from U(M
hβ h )4 ,M hβ hv −1 ,M β hv
to be performed in each extract-min leaf encountered before v in a pre-order traversal of T are
completely fixed under distribution D(β, h, M ). Thus we assume Alice and Bob also both know
these operations. Furthermore, Bob can privately determine all operations to be performed in the
extract-min leaves in the subtrees rooted at c2 (v), . . . , ck−1 (v) if following distribution D(β, h, M ).
We are ready to describe the communication protocol.

The Two-Phase Communication Protocol. In the first phase, Alice and Bob first send the
bits needed by the rejection sampling procedure described above. Next, from the sampling above,
Alice and Bob both know all updates of all leaves in the sampled T encountered before v in a preorder traversal of T . They both privately run the deterministic priority queue Q on this update
sequence. Next, Bob knows all updates in c1 (v), . . . , ck−1 (v). He privately feeds these updates to
the priority queue Q and remembers the set of addresses A of the cells changed by these updates.
He sends the set of such addresses to Alice for O(|A|w) bits. He also sends the memory contents of
9

Q for another O(M w) bits. Alice now starts running the updates of the subtree ck (v) (she knows all
these operations, except for the Inserts in the extract-min leaves). When processing these updates,
whenever they want to read a cell for the first time during the updates of ck (v), Alice checks if the
cell’s address is in A. If not, she knows the correct contents of the cell from her own simulation of
the data structure up to just before v. Otherwise, she asks Bob for the contents of the block (costing
O(w) bits to specify the address) as it is just before processing ck (v) and Bob replies with its O(Bw)
bit contents. From that point on, Alice will remember all changes to that cell. Observe that by this
procedure, when reaching an ExtractMin leaf, she can first simulate the query algorithm of Q on all
the ExtractMin operations. From the answers to these, she knows which Inserts to perform in the
extract-min leaf in order to follow distribution D(β, h, M ), so she runs these Inserts as well. Once
Alice has finished running all updates in the subtree ck (v), phase one ends. In phase two, Alice
starts by collecting the set of addresses Z of all cells changed by the updates in ck (v)’s subtree.
She sends this set of addresses to Bob for O(|Z|w) bits. She also sends the memory contents of Q
after processing all updates in ck (v)’s subtree. This costs O(M w) vits. Bob now starts running
all updates in ck+1 (v), . . . , c2+β (v) on Q. Each time one of these updates reads a cell with an
address in Z for the first time, Bob asks Alice for the contents of the block and Alice replies.
This costs O(w) bits from Bob and O(Bw) bits from Alice. If a block not with an address in Z
is read, Bob knows the contents himself. When Bob runs the ExtractMin operations in c2+β (v),
he remembers the returned key-priority pairs (k1 , p1 ), . . . , (kM hβ kv , pM hβ kv ). It follows from our
distribution D(β, h, M ) that Y ∩ X is precisely the set of keys that were inserted during c1 (v), not
deleted in any of the delete-leaves in the subtrees rooted at c2 (v), . . . , ck−1 (v), ck+1 (v), . . . , c1+β (v)
and yet was not returned with priority hv by an ExtractMin operation in c2+β (v). But Bob knows
all these things, so he can compute Y ∩ X. He then sends this set to Alice for O(|X ∩ Y | lg N ) bits,
finishing the communication protocol.
Analysis. What remains is to analyse the efficiency of the Two-Phase protocol above. First
observe that L and K are both at most N = M hβ h and the same for |X| and |Y |. Since the
universe has size N 4 , the probability of having to reject the sampled sets are less than 1/N 2 . So
the expected communication due to rejection sampling is O(1) bits for both players. Now since
the distribution of the update sequence fed to Q is D(β, h, M ), it follows from Lemma 2 that
E[|A|w] ≤ E[C(v)w] = O(max{tI , tD , tE }M hwβ hv ) = O(max{tI , tD , tE }hw|Y |). Since hv ≥ h/2,
we see that O(M w) = o(|Y |). Next, observe that the number of cells for which Alice needs to
ask Bob for the contents in phase one is |R(v, k)|. Thus the expected number of bits sent by
Alice to ask for cell contents is O(max{tI , tD , tE }M β hv −1 w) = O(max{tI , tD , tE }M β hv −1 w) =
O(max{tI , tD , tE }|X|w/h). Bob’s replies cost an expected
O(max{tI , tD , tE }M β hv −1 Bw) = O(max{tI , tD , tE }|Y |Bw/β)
bits.
For phase two, sending the addresses of cells in Z cost an expected
E[|Z|w] ≤ E[C(v)w] = O(max{tI , tD , tE }M hwβ hv ) = O(max{tI , tD , tE }βw|X|)
bits. Since hv ≥ h/2, we have O(M w) = o(|X|). Next, the number of cells for which Bob needs to
ask Alice for the contents is |L(v, k)|. Thus the expected number of bits sent by Bob to ask for cell
contents is O(max{tI , tD , tE }M β hv −1 w) = O(max{tI , tD , tE }|Y |w/β). The replies of Alice costs
expected O(max{tI , tD , tE }M Bβ hv −1 w) = O(max{tI , tD , tE }Bw|X|/h) bits. Finally, the expected
size of |X ∩ Y | is O(1/N 2 ) bits, thus the last message from Bob to Alice (sending X ∩ Y ) costs and
expected O(1) bits.
10

Deriving the Lower Bound. From the bounds on the communication, we can finally derive
our lower bound. First observe that the lower bound in Theorem 2 is trivial for B = lgc N for
any constant c > 0 (it only claims Ω(1/B)). Thus we focus on the case of B = lgω(1) N . We set
′
β = lgc N for a sufficiently large constant c′ > 0. Since we assume N ≥ M 1+ε for some constant
ε > 0, we get that with this choice of β, we have h = Θ(lg N/ lg lg N ). Now assume for contradiction
that max{tI , tD , tE } = o((1/B) lg lg N B). The analysis above now shows that the priority queue Q
SI
(i.e. |X| = M hβ hv −1 and
can be used to obtain a Two-Phase protocol for U(M
hβ h )4 ,M hβ hv −1 ,M β hv

|Y | = M β hv = ω(|X|)) in which the costs are the following:

• In phase one, Alice sends o(((1/B) lg lg N B)|X|w/h) = o(|X|).
• In phase one, Bob first sends o(((1/B) lg lg N B)hw|Y |) + o(|Y |) = o(|Y |) bits. He then sends
o(((1/B) lg lg N B)|Y |Bw/β) = o(|Y |(w lglg N B)/β) = o(|Y |)
bits.
• In phase two, Alice first sends o(((1/B) lg lg N B)βw|X|) + o(|X|) = o(|X|) bits. She then
sends o(((1/B) lg lg N B)Bw|X|/h) = o(|X| lg B) bits.
√
• In phase two, Bob sends o(((1/B) lg lg N B)|Y |w/β) = o(|Y |/ B) bits.
Thus under our contradictory assumption, we have obtained a Two-Phase protocol P for
SI
U(M
hβ h )4 ,M hβ hv −1 ,M β hv

√
SI
B)). But this is impossible by Lemma 1.
of cost C(P, UN
4 ,|X|,|Y | ) = (o(|X|), o(|Y |), o(|X| lg B), o(|Y |/
We therefore conclude that max{tI , tD , tE } = Ω((1/B) lglg N B), completing the proof of Theorem 2
and thus also Theorem 1.
To summarize the main technical idea in our proof, the first phase corresponds to probes made
by child ck (v). These probes are simulated by Alice and thus she will be asking for cell contents.
Since a cell address costs a factor B less to specify than its contents, Alice will be very silent in
phase one. In phase two, Bob is simulating the probes made by ck+1 (v), . . . , c2+β (v) into ck (v).
Therefore, he is asking for cell contents and his communication is factor B less than what Alice
needs to say to reply with cell contents. Thus one can interpret the Two-Phase communication
lower bound as saying: if the data structure does not read enough cells from c1 (v) while processing
Deletes in ck (v)’s subtree (small communication in phase one), then the priority queue has not
learned which Deletes in ck (v)’s subtree that correspond to keys inserted in c1 (v). It therefore
cannot structure the Deletes into a nice data structure supporting efficient ExtractMins in c2+β (v)
(phase two).

3.3

Avoiding Deletes of Keys not in the Priority Queue

Recall that we assumed above that we are allowed to perform Delete operations on keys not in
the priority queue, and that such spurious Deletes have no effect. We show in the following how
to modify our proof such that the lower bound is derived for a sequence of operations that never
delete a key not present in the priority queue.
In the previous sections, the hard distribution is defined solely from the tree T . The tree T
defines O(N ) operations on key-priority pairs with keys from a universe of size O(N 4 ). Here is
how to modify the distribution to avoid Deletes on non-inserted elements: Before performing the
11

updates in T , start by inserting all keys in the universe, with priorities ∞ (or some priority larger
than all priorities ever used by T ). Note that this gives O(N 4 ) updates, not O(N ). Therefore,
we perform updates corresponding to N 3 independently chosen trees T1 , T2 , . . . , TN 3 , one after the
other. Since the lower bound proved in the previous section only has lg N or lg B’s and we scale the
number of operations N by a polynomial factor, the asymptotic lower bound does not change and
we can just zoom in on one tree that performs well in expectation and do the same analysis as above.
This of course creates the problem that a tree has to ”clean up” to make sure that after processing
a tree Ti , all keys are again in the priority queue with priority ∞. This needs further modifications:
Every Insert operation in a tree T is transformed into two operations: first a Delete on the key that
we are about to insert, and then the Insert. This ensures we never insert anything already there.
Every Delete operation in the tree is transformed into two operations: First the Delete operation,
and then an Insert with the same key, but priority ∞. Finally, all extract-min leaves are augmented
as follows: Extract-min leaves already re-insert all key-priority pairs extracted with a priority not
matching the current level of the tree. We do not change that. But the extract-min leaves also
effectively removes those keys that match in priority. We therefore add an Insert for those keys, now
having priority ∞. In this way, Alice and Bob can still solve the set disjointness communication
game, and we never delete a key not present in the priority queue. The only extra requirement this
transformation introduces, is that we now must have N 1/4 ≥ M 1+ε , i.e. N ≥ M 4+ε .

4

Proof of the Communication Lower Bound

In this section, we are going to prove Lemma 1, a Two-Phase communication lower bound for the
set intersection problem on uniformly random inputs.
SI
for SetIntU,k,l Alice’s input X is sampled from all
Hard distribution UU,k,l
of size k uniformly at random. Independently, Bob’s input Y is sampled from all
of size l uniformly at random.

U
k  subsets
U
l subsets

of [U ]
of [U ]

Restatement of Lemma 1. No Las Vegas Two-Phase protocol P for SetIntU,k,l can have
SI
) = (o(k), o(l), o(k lg B), o(k/B))
C(P, UU,k,l

for any B > 1, l ≫ k and U ≫ l.
The main idea is to apply information complexity arguments and do a chain of reductions:
1. (Proof of Lemma 1) Since we are sampling k elements uniformly at random from [U ] for
Alice’s input X, and l elements for Bob’s input Y for l ≫ k, we would expect that if the
universe is divided into k blocks evenly, then many blocks will have exactly one element in
X, and if we further divide each block into l/k buckets, many buckets will have exactly one
element in Y . In this step, we show that if there is an efficient way to solve the problem on
all uniform inputs, then there is way to solve it on inputs where every block [bucket resp.]
has exactly one element in X [Y resp.].
2. (Proof of Lemma 7) Since the k blocks are disjoint, we are actually solving k independent
instances of the problem where Alice has one element and Bob has l/k elements, one in each
bucket. We show that if such protocol exists, we can solve one instance with 1/k of the
information cost of the original protocol.

12

3. (Proof of Lemma 6) In this step, we eliminate Phase I. Alice has only one element, so her input
can be viewed as a pair: (bucket number, offset within the bucket). They just want to know
if Bob’s element in this bucket has exactly the same offset. We show that since Alice and Bob
do not talk too much in Phase I, there is way to fix the transcript such that conditioned on
the transcript, neither Alice nor Bob have revealed too much information about their offsets.
We will show that even if the bucket number of Alice’s input is revealed to Bob at the end of
Phase I, the problem is still hard. In this case, their Phase II is just equality testing (offsets
within the bucket) with inputs close to uniformly random.
4. (Proof of Lemma 5) In this step, we actually “separate” the communication in Phase I and
Phase II. Although we have already eliminated Phase I in the previous step, if we try to
apply rectangle argument directly, it turns out we will just end up adding the information
cost of the two phases together in the proof. Thus, before applying any real lower bound
argument, we first show that if the inputs are close to uniform, there will be a large subset of
the universe such that each of them occurs with decent probability. The input distribution
can be viewed as a convex combination of, the uniform distribution on this smaller set (with
constant weight), and some other distribution. That is, with constant probability, they are
actually solving the problem on a smaller universe, but with uniform inputs. This shows that
the protocol can solve the uniform input with a constant factor blow-up in the information
cost.
5. (Proof of Lemma 4) Apply the standard rectangle argument, we prove a lower bound for the
uniform input case.
As a tool heavily used in the chain of reductions, we define the information cost of a protocol
P on input distribution µ as follows:
Definition 1. We say I(P, µ) = (a1 , b1 , a2 , b2 ), if
priv
1. I(X; Π1 |Y, Rpub , RB
) ≤ a1 ;
priv
2. I(Y ; Π1 |X, Rpub , RA
) ≤ b1 ;
priv
3. I(X; Π2 |Y, Π1 , Rpub , RB
) ≤ a2 ;
priv
4. I(Y ; Π2 |X, Π1 , Rpub , RA
) ≤ b2 ,

where Π1 is the transcript generated by P on input pair (X, Y ) in Phase I, Π2 is the transcript of
priv
priv
Phase II, Rpub is the public coin, and RA
and RB
are the private coins used by Alice and Bob
respectively.
That is, in Phase I, Alice reveals at most a1 bits of information, Bob reveals at most b1 ; in
Phase II, Alice reveals at most a2 bits of information and Bob reveals at most b2 .
As in the standard communication model, information cost is always a lower bound of communication cost, i.e., I(P, µ) ≤ C(P, µ). Since we always work with product input distributions in
this section, by the following fundamental lemma about communication complexity, the definition
priv
priv
remains equivalent if all conditions on X, Y, RA
, RB
are removed.
Lemma 3. For production distribution on input pair (X, Y ), conditioned on a (prefix of a) tranpriv
priv
script Π = π and public coin flips Rpub = r pub , (X, RA
) and (Y, RB
) are independent.
The lemma can be proved by induction, we will omit its proof here. In the following, we start
by proving a lower bound for the base problem EQ, then we will build hardness on top of it.
13

The EQ problem and hard distribution UW × UW Alice and Bob receive two independent
uniform random number from set [W ]. Their goal for EQ is to determine whether the two numbers
equal.
Lemma 4. For any Las Vegas (standard One-Phase) protocol Peq for EQ, let Π be the random tranpriv
priv
script Peq generated on (Xeq , Yeq ) ∼ UW × UW with public coins Rpub and private coins RA
, RB
,
Peq cannot have both
1
I(Xeq ; Π|Rpub ) ≤ lg B,
2
and
1
I(Yeq ; Π|Rpub ) ≤
2B
for any B > 1 and W ≥ 2.
Proof. Assume for contradiction, such protocol Peq exists. Then by definition, we have
1
lg B ≥ I(Xeq ; Π|Rpub )
2
= H(Xeq ) − H(Xeq |Π, Rpub )

= Eπ,rpub [H(Xeq ) − H(Xeq |Π = π, Rpub = r pub )]

Note that Xeq is uniform, the difference inside the expectation is always non-negative. By Markov’s
inequality, with ≥ 1/2 probability,
H(Xeq |Π = π, Rpub = r pub ) ≥ H(Xeq ) − lg B.
Similarly, with ≥ 1/2 probability,
H(Yeq |Π = π, Rpub = r pub ) ≥ H(Yeq ) − 1/B.
Thus, by union bound, there exist some π and r pub such that both conditions hold.
However, since Peq is zero-error, conditioned on Π = π and Rpub = r pub , the set of all values for
Xeq that occur with non-zero probability and the set of all values for Yeq that occur with non-zero
probability must form a monochromatic rectangle. Thus, these two sets of values must be pairwise
distinct (or pairwise equal, in which case we also have the following), implying
pub =r pub )

2H(Xeq |Π=π,R

pub =r pub )

+ 2H(Yeq |Π=π,R

≤ W.

However, we also have
pub =r pub )

2H(Xeq |Π=π,R

pub =r pub )

+ 2H(Yeq |Π=π,R

≥ 2lg W −lg B + 2lg W −1/B

= W (2− lg B + 2−1/B )


ln 2
1
+ e− B
=W
B


1
ln 2
+1−
≥W
B
B
> W.
We have a contradiction, such protocol does not exist.
14

The following lemma shows that even if the input distribution is slightly non-uniform, the
problem is still hard.
Lemma 5. Fix any two distributions DX and DY over [V ], such that for Xeq ∼ DX and Yeq ∼ DY ,
H(Xeq ) ≥ lg V − 1/18 and H(Yeq ) ≥ lg V − 1/18. Then for any Las Vegas (One-Phase) protocol
Peq for EQ, let Π be the random transcript Peq generated on (Xeq , Yeq ) ∼ DX × DY , with public
priv
priv
coins Rpub and private coins RA
, RB
, then Peq cannot have both
I(Xeq ; Π|Rpub ) ≤

1
lg B,
12

and
I(Yeq ; Π|Rpub ) ≤

1
12B

for any B > 1 and V ≥ 6.
Note that we cannot hope to increase the 1/18 in the statement to 1, as then DX and DY can
have completely disjoint support.
Proof. Assume for contradiction, such protocol Peq exists. Then by Pinsker’s inequality,
r
r
1
1
δ(DX , UV ) ≤
DKL (DX kUV ) =
(lg V − H(Xeq )) ≤ 1/6.1
2
2

1
, we must have |WX | ≥ 23 V . Otherwise,
Let WX = x : PrDX [Xeq = x] ≥ 2V
 DX and UV on 1the
,
event Xeq 6∈ WX will have difference more than 1/6. Similarly, let WY = y : Pr[Yeq = y] ≥ 2V
2
1
we have |WY | ≥ 3 V . Let W = WX ∩ WY , by union bound, |W | ≥ 3 V .
The distribution DX [DY resp.] can be viewed as a convex combination of two distributions:
the uniform distribution UW over W with weight 1/6, and some other distribution D X [D Y resp.]
with weight 5/6. Note that such decompositions are possible whenever
Pr

Xeq ∼DX

[Xeq = x] ≥

and
Pr [Yeq = y] ≥

Yeq ∼DY

1
Pr [Xeq = x]
6 Xeq ∼UW
1
Pr [Yeq = y]
6 Yeq ∼UW

hold for every x and y.
Thus, to sample an input pair (Xeq , Yeq ) ∼ DX × DY , we can think of it as a two-step process:
first decide independently for Xeq [Yeq resp.], whether to sample them from UW or DX [D Y resp.],
then sample them from the corresponding distribution. Let CX [CY resp.] be the random variable
indicating the outcome of the first step (taking value 0 indicates sampling from UW ). We are going
′ ,Y ′ ) ∼ U
to show that the Las Vegas protocol Peq itself is too good for input pair (Xeq
W × UW .
eq
′
′
′
Let Π be the (random) transcript generated by Peq on (Xeq , Yeq ) with public coin Rpub′ .
′ ; Π′ |Rpub′ ) = I(X ; Π|Rpub , C = 0). On the one hand,
We have I(Xeq
eq
X
I(Xeq ; Π|Rpub , CX ) =
1

1
5
I(Xeq ; Π|Rpub , CX = 0) + I(Xeq ; Π|Rpub , CX = 1).
6
6

δ(P, Q) := supeventA |P (A) − Q(A)|.

15

On the other hand,
I(Xeq ; Π|Rpub , CX ) = I(Xeq , CX ; Π|Rpub ) − I(CX ; Π|Rpub )

= I(Xeq ; Π|Rpub ) + I(CX ; Π|Rpub , Xeq ) − I(CX ; Π|Rpub )

≤ I(Xeq ; Π|Rpub ).

The last inequality is using the fact that conditioned on Xeq , CX is independent of (Π, Rpub ), and
′ ; Π′ |Rpub′ ) ≤ 6I(X ; Π|Rpub ) ≤ 1 lg B. Similarly,
thus I(CX ; Π|Rpub , Xeq ) = 0. Therefore, I(Xeq
eq
2
1
′
′
pub′
pub
we have I(Yeq ; Π |R
) ≤ 6I(Yeq ; Π|R ) ≤ 2B . However, this is impossible for any Las Vegas
protocol by Lemma 4.
IE
The IndEqV,L problem and hard distribution DV,L
Alice receives X = (F, O), where F is
a uniformly random number in [L], and O is a uniformly random number in [V ]. Bob receives
Y = (Y1 , . . . , YL ), where each Yi is a uniformly random number in [V ]. Their goal is to decide
whether O = YF .

Lemma 6. No Las Vegas Two-Phase protocol Pie for IndEqV,L can have
IE
I(Pie , DV,L
)

=



L lg B 1
1
,
,
,
216 288 144 48B



for any B > 1 and V ≥ 6.
Proof. Assume for contradiction, such protocol P exists. Let Xie = (F, O) and Yie = (Y1 , . . . , YL ).
By definition, we have
1. I(F, O; Π1 |Rpub ) ≤

1
216 ;

2. I(Y1 , . . . , YL ; Π1 |Rpub ) ≤
3. I(X; Π2 |Π1 , Rpub ) ≤

lg B
144 ;

4. I(Y ; Π2 |Π1 , Rpub ) ≤

1
48B .

L
288 ;

By the first inequality above and the fact that public coin is independent of the input, we have
1
≥ H(F, O) − H(F, O|Π1 , Rpub )
216
h

i
= Eπ1 ,rpub H(F, O) − H(F, O|Π1 = π1 , Rpub = r pub ) .

Since (F, O) is uniform, the difference inside the expectation is always non-negative. By Markov’s
inequality, with probability ≥ 3/4,
H(F, O) − H(F, O|Π1 = π1 , Rpub = r pub ) ≤

1
.
54

That is, H(F, O|Π1 = π1 , Rpub = r pub ) ≥ lg L + lg V − 1/54. Similarly, with probability ≥ 3/4,
H(Y1 , . . . , YL |Π1 = π1 , Rpub = r pub ) ≥ L · lg V − L/72. By Markov’s inequality again, with proba1
lg B and with probability ≥ 3/4, I(Y ; Π2 |Π1 =
bility ≥ 3/4, I(X; Π2 |Π1 = π1 , Rpub = r pub ) ≤ 36
1
pub
pub
π1 , R
= r ) ≤ 12B . Thus, by union bound, there exists some (π1 , r pub ) such that all four
inequalities hold:
16

1. H(F, O|Π1 = π1 , Rpub = r pub ) ≥ lg L + lg V −

1
54 ;

2. H(Y1 , . . . , YL |Π1 = π1 , Rpub = r pub ) ≥ L · lg V −
3. I(F, O; Π2 |Π1 = π1 , Rpub = r pub ) ≤

1
36

L
72 ;

lg B;

4. I(Y1 , . . . , YL ; Π2 |Π1 = π1 , Rpub = r pub ) ≤

1
12B .

That is, conditioned on (Π1 , Rpub ) = (π1 , r pub ), the inputs still have high entropy and the players
do not reveal too much information about their inputs in Phase II. We are going to show that it is
impossible by Lemma 5. From now on, we fix π1 and r pub and condition on Π1 = π1 , Rpub = r pub .
1. By chain rule, we have
H(O|Π1 = π1 , Rpub = r pub , F ) = H(F, O|Π1 = π1 , Rpub = r pub )
− H(F |Π1 = π1 , Rpub = r pub )

≥ H(F, O|Π1 = π1 , Rpub = r pub ) − lg L

≥ lg V − 1/54.

By Markov’s inequality, H(O|Π1 = π1 , Rpub = r pub , F = f ) ≥ lg V − 1/18 with at least 2/3
probability (over a random f ).
2. By sub-additivity of entropy,
L
X
f =1

H(Yf |Π1 = π1 , Rpub = r pub ) ≥ L · lg V − L/72.

Since each H(Yf |Π1 = π1 , Rpub = r pub ) ≤ lg V , by Markov’s inequality, at least 3L/4 different
f ’s have H(Yf |Π1 = π1 , Rpub = r pub ) ≥ lg V − 1/18. These f ’s must occur with high
probability, since F has high entropy: H(F |Π1 = π1 , Rpub = r pub ) ≥ lg L − 1/54. In fact, if
we had
i
h
X
Pr F = f |Π1 = π1 , Rpub = r pub < 2/3,
f :H(Yf |Π1 =π1 ,Rpub =r pub )≥lg V −1/18

then by the concavity of p lg 1p , we would have
2 0.75L 1 0.25L
lg
+ lg
3
2/3
3
1/3
2 9L 1 3L
= lg
+ lg
3
8
3
4
1 256
= lg L − lg
3 243
< lg L − 1/40.

H(F |Π1 = π1 , Rpub = r pub ) <

Thus, by Lemma 3, H(YF |Π1 = π1 , Rpub = r pub , F = f ) ≥ lg V − 1/18 with probability at
least 2/3 (over a random f ).

17

3. By chain rule,
I(O; Π2 |Π1 = π1 , Rpub = r pub , F ) = I(F, O; Π2 |Π1 = π1 , Rpub = r pub )
− I(F ; Π2 |Π1 = π1 , Rpub = r pub )
1
lg B.
≤
36

By Markov’s inequality, I(O; Π2 |Π1 = π1 , Rpub = r pub , F = f ) <
least 2/3 (over a random f ).

1
12

lg B with probability at

4. By Lemma 3, we have
I(YF ; Π2 |Π1 = π1 , Rpub = r pub , F = f ) = I(Yf ; Π2 |Π1 = π1 , Rpub = r pub )
≤ I(Y ; Π2 |Π1 = π1 , Rpub = r pub )
1
≤
.
12B

Thus, by union bound, there is some f ∈ [L], such that
0. by Lemma 3, O and YF are independent conditioned on Π1 = π1 , Rpub = r pub , F = f ;
1. H(O|Π1 = π1 , Rpub = r pub , F = f ) ≥ lg V − 1/18;
2. H(YF |Π1 = π1 , Rpub = r pub , F = f ) ≥ lg V − 1/18;
3. I(O; Π2 |Π1 = π1 , Rpub = r pub , F = f ) ≤

1
12

4. I(YF ; Π2 |Π1 = π1 , Rpub = r pub , F = f ) ≤

lg B;

1
12B .

That is, when Π1 = π1 , Rpub = r pub , F = f , Phase II of protocol P can decide if YF = O with
low information cost, while both inputs YF and O have high entropy. However, Lemma 5 asserts
that it is impossible.
SI
for SetIntU,k,l Partition [U ] into k blocks {A1 , . . . , Ak } of size U/k,
Hard distribution DU,k,l
and partition each block Ai further into l/k buckets {Bi,1 , . . . , Bi,l/k } of size U/l. Alice’s input set
X contains one uniformly random element from each Ai for 1 ≤ i ≤ k, Bob’s input set Y contains
one uniformly random element from each Bi,j for 1 ≤ i ≤ k and 1 ≤ j ≤ l/k. Thus, X is a subset
of [U ] of size k, and Y is a subset of size l.
Note that by associating each bucket a number Yi , and represent X as the pair (bucket numSI
ber, offset in the bucket), the SetIntU/k,1,l/k problem on DU/k,1,l/k
is equivalent to the IndEqU/l,l/k
IE
problem on DU/l,l/k .

Lemma 7. No Las Vegas Two-Phase protocol Psi for SetIntU,k,l can have


l k lg B k
k
SI
,
,
,
,
)=
I(Psi , DU,k,l
216 288 144 48B
as a consequence, no Psi can have
SI
)=
C(Psi , DU,k,l



l k lg B k
k
,
,
,
216 288 144 48B

for any B > 1, U ≥ 6l.
18



Proof. Assume for contradiction, such protocol Psi exists. We show that it can be used to solve
IE
IndEqU/l,l/k on DU/l,l/k
efficiently by a standard information complexity argument.
IE
Given Psi , consider the following protocol Pie on input pair (Xie , Yie ) ∼ DU/l,l/k
:
1. Use public coin to uniformly sample a random I from the set {1, . . . , k}.
SI .
2. Generate an input pair (X, Y ) for SetIntU,k,l . Partition [U ] into {A1 , . . . , Ak } as for DU,k,l
For block AI , add the corresponding elements in Xie and Yie to X and Y respectively, i.e., for
Xie = (F, O), Alice adds O + (F − 1)U/l + (I − 1)U/k to X, and for each Yf in Yie, Bob adds
Yf + (f − 1)U/l + (I − 1)U/k to Y . For all other blocks, they use private coin to sample the
SI , i.e., Alice samples one uniformly random element from the
elements for (X, Y ) as in DU,k,l
block, Bob further partitions it into l/k buckets and samples one uniformly random element
IE
SI .
from each of them. It is not hard to see that if (Xie , Yie ) ∼ DU/l,l/k
, then (X, Y ) ∼ DU,k,l

3. Run protocol Psi on (X, Y ) to compute the intersection X ∩ Y , and return the set X ∩ Y ∩ AI
(with a shift of −(I − 1)U/k).
Since different blocks are disjoint, the set X ∩ Y ∩ AI tells the players whether YF = O. Thus,
as long as Psi is zero-error (for SetIntU,k,l ), Pie is also a zero-error protocol (for IndEqU/l,l/k ). To
analyze its information cost, let X (i) = X ∩ Ai , we have
I(Xie ; Π1 |R

pub

k
1X
I(Xie ; Π1 |I = i, Rpub (Psi ))
)=
k

=

1
k

i=1
k
X
i=1

I(X (i) ; Π1 |I = i, Rpub (Psi ))

k
1X
=
I(X (i) ; Π1 |Rpub (Psi ))
k
i=1

1
≤ I(X; Π1 |Rpub (Psi ))
k
1
≤
,
216
where Rpub (Psi ) is the random coins used in Psi .
l
1
Similar arguments also prove that I(Yie ; Π1 |Rpub ) ≤ 288k
, I(Xie ; Π2 |Π1 , Rpub ) ≤ 144
lg B and
1
pub
I(Yie ; Π2 |Π1 , R ) ≤ 48B . But by Lemma 6 (setting V = U/l and L = l/k), such protocol does
not exist.
Finally, we are ready to prove Lemma 1, a communication lower bound for SetIntU,k,l on uniSI .
formly random inputs (X, Y ) ∼ UU,k,l
Proof of Lemma 1. Assume for contradiction, such protocol P exists. We are going to design a
SI
“too good” protocol for SetIntU/9,k/9,l/9 and input distribution DU/9,k/9,l/9
.
Partition [U ] into l buckets of size U/l each. Bob’s input set Y is sampled uniformly from all
U
l subsets of [U ] of size l. We can think of the sampling of Y being a two-step process: first decide
the number of elements of Y in each bucket, then sample a uniformly random subset of this size
from the bucket. Intuitively, with high probability, there will be a constant fraction of the buckets
that are going to have exactly one element after the first step, which is stated as the following
observation:
19

Observation 1. The probability that at least l/3 buckets have exactly one element is 1 − o(1).
In order to focus on proving our communication lower bound, we defer the proof of the observation to the end of the section. Assume this happens, then group these l/3 buckets into k/3 blocks,
each of which consists of l/k buckets. We now think of X also being sampled by a two-step process: first decide the number of elements of X in each block (which also determines the number of
elements outside these l/3 buckets), then sample uniformly random sets of the corresponding sizes
from the blocks (and from the elements not in any block). A similar argument as Observation 1
shows that the probability that at least k/9 blocks that are going to have exactly one element with
probability 1 − o(1). Call these k/9 blocks the good blocks, and their l/9 buckets the good buckets.
SI
Consider the following protocol Psi for SetIntU/9,k/9,l/9 on input (Xsi , Ysi ) ∼ DU/9,k/9,l/9
:
SI in the following way. Complete the first steps of sampling X and Y as
1. Generate (X, Y ) ∼ UU,k,l
described above using public coin (which fails with o(1) probability). If it does not fail, for the
k/9 good blocks and their l/9 good buckets, embed Xsi and Ysi into them. For all other blocks
SI
and buckets, complete the second steps of sampling. Thus, when (Xsi , Ysi ) ∼ DU/9,k/9,l/9
, we
SI
have (X, Y ) ∼ UU,k,l .

2. If the sampling fails, repeat Step 1. Otherwise, run P on (X, Y ), and return the intersection
in the good blocks.
It is not hard to verify that Psi solves SetIntU/9,k/9,l/9 with zero-error and communication cost
(o(k), o(l), o(k lg B), o(k/B)). By Lemma 7, such protocol does not exist, and we have a contradiction.
Proof of Observation 1. Let ξi be the random variable
P indicating whether i-th bucket has exactly
one element of Y (ξi = 1 indicates YES). Let ξ = li=1 ξi . Thus, by Stirling’s formula,
E[ξi ] = Pr[ξi = 1]
U −U/l
· U/l
= l−1 U 
l

(U/l)l−1 (1 − U/l)U −U/l−l+1 U
·
∼
(U/l)l (1 − U/l)U −l
l

= (1 − U/l)−U/l+1

∼ e−1

By linearity of expectation, E[ξ] ∼ e−1 l. On the other hand,
E[ξi ξj ] = Pr[ξi = 1 ∧ ξj = 1]
U −2U/l
· (U/l)2
l−2
=

U
l

(U/l)l−2 (1 − U/l)U −2U/l−l+2 U 2
· 2
∼
(U/l)l (1 − U/l)U −l
l
= (1 − U/l)−2U/l+2

∼ e−2 .

20

Thus, we have
Var[ξ] = E[ξ 2 ] − (E[ξ])2
=

l
X

E[ξi2 ] + 2

i=1

X
i<j

−1

= (1 + o(1))e
= o(l2 ).

E[ξi ξj ] − (1 + o(1))e−2 l2

l + l(l − 1)(1 + o(1))e−2 − (1 + o(1))e−2 l2

By Chebyshev’s inequality, we have Pr[ξ < l/3] ≤ o(1), which proves the observation.

References
[1] A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems.
Communications of the ACM, 31:1116–1127, 1988.
[2] G. S. Brodal. Worst-case efficient priority queues. In Proc. 7th ACM/SIAM Symposium on
Discrete Algorithms, SODA ’96, pages 52–58, 1996.
[3] G. S. Brodal and R. Fagerberg. Lower bounds for external memory dictionaries. In Proc. 14th
ACM/SIAM Symposium on Discrete Algorithms, SODA ’03, pages 546–554, 2003.
[4] J. Brody, A. Chakrabarti, R. Kondapally, D. P. Woodruff, and G. Yaroslavtsev. Beyond set
disjointness: The communication complexity of finding the intersection. In Proc. 2014 ACM
Symposium on Principles of Distributed Computing, PODC ’14, pages 106–113, 2014.
[5] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press,
Cambridge, Mass., 1990.
[6] R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola. Heaps and heapsort on secondary
storage. Theoretical Computer Science, 220(2):345–362, June 1999.
[7] M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596–615, July 1987.
[8] Y. Han. Deterministic sorting in o(nlog log n) time and linear space. In Proc. 34th ACM
Symposium on Theory of Computation, STOC ’02, pages 602–608, 2002.
√
[9] Y. Han and M. Thorup. Integer sorting in O(n lg lg n) expected time and linear space. In
Proc. 43rd IEEE Symposium on Foundations of Computer Science, pages 135–144, 2002.
[10] J. Iacono and M. Pǎtraşcu. Using hashing to solve the dictionary problem (in external memory). In Proc. 23rd ACM/SIAM Symposium on Discrete Algorithms, pages 570–582, 2012.
[11] V. Kumar and E. J. Schwabe. Improved algorithms and data structures for solving graph
problems in external memory. In Proc. 8th IEEE Symposium on Parallel and Distributed
Processing, SPDP ’96, pages 169–, 1996.
[12] U. Meyer and N. Zeh. I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths,
pages 540–551. 2006.

21

[13] P. Miltersen, N. Nisan, S. Safra, and A. Wigderson. On data structures and asymmetric
communication complexity. Journal of Computer and System Sciences, 57(1):37–49, 1998.
[14] M. Thorup. Integer priority queues with decrease key in constant time and the single source
shortest paths problem. Journal of Computer and System Sciences, 69(3):330–353, 2004.
[15] M. Thorup. Equivalence between priority queues and sorting. Journal of the ACM, 54(6),
Dec. 2007.
[16] E. Verbin and Q. Zhang. The limits of buffering: a tight lower bound for dynamic membership
in the external memory model. In Proc. 42nd ACM Symposium on Theory of Computation,
pages 447–456, 2010.
[17] Z. Wei and K. Yi. Equivalence between priority queues and sorting in external memory. In
Proc. 22nd European Symposium on Algorithms, pages 830–841, 2014.
[18] A. C.-C. Yao. Should tables be sorted? Journal of the ACM, 28(3):615–628, 1981.
[19] K. Yi and Q. Zhang. On the cell probe complexity of dynamic membership. In Proc. 21st
ACM/SIAM Symposium on Discrete Algorithms, pages 123–133, 2010.

A

Internal Memory DecreaseKeys

In the following, we show how we one can support the DecreaseKey operation at no loss of efficiency
for Las Vegas randomized and amortized internal memory data structures when the keys can be
efficiently hashed (i.e. one can construct a hash table with expected amortized O(1) time lookups).
We first describe it in the case where keys are never re-inserted after having been extracted.
Given a priority queue supporting only Insert and ExtractMin, we modify it to support DecreaseKeys. Let tI (N ) be its expected amortized insert time when storing N elements and let
tE (N ) be its expected amortized ExtractMin time. We start by supporting DecreaseKeys in expected amortized O(tI (N ′ ) + tE (N ′ )) time per operation over a sequence of N ′ operations if we are
promised that a key is never re-inserted into the priority queue after having been extracted. This
is done as follows: We keep a counter C on the number of operations performed on the priority
queue. The counter C is initialized to 0, and on each operation we increment it by 1. In addition
to C, we maintain a priority queue Q supporting only Insert and ExtractMin, as well as a hash
table H. The hash table H will store the keys that have already been extracted. In more detail,
on an Insert(k, p), we create the key k ◦ C, i.e. we augment the key with the time of the operation
and assume that the data structure treats two keys k ◦ C and k ◦ C ′ as distinct keys. We then
insert (k ◦ C, p) in Q by running its Insert operation. On a DecreaseKey(k, p), we create the key
k ◦ C and run Insert(k ◦ C, p) on Q. On ExtractMin, we run ExtractMin on Q. This returns a pair
(k ◦ Ck , p), where Ck is the time when k either underwent an Insert or a DecreaseKey. We then
do a lookup in H for k. If k is not in H, we simply return (k, p) as our result and insert k in H.
If k is in H, we know the key has already been extracted with a smaller priority. We then invoke
ExtractMin on Q again until we find a key-priority pair that have not yet been extracted.
Since we assume hash tables can be implemented with O(1) expected amortized time operations,
and each DecreaseKey operation causes one Insert and one ExtractMin, the size of Q is thus O(N ′ )
where N ′ is the number of operations performed on the priority queue. Therefore the expected
amortized cost of the DecreaseKey is O(tI (N ′ ) + tE (N ′ )).
If we assume keys can be re-inserted after having been extracted, we can store an additional
hash table with the last time at which an Insert on a given key was performed. Then when running
22

ExtractMin and seeing a pair (k ◦ Ck , p), we also check the value of Ck to see if it is lower than the
last time k was inserted. In that case, we also throw away the pair and run another ExtractMin
on Q.
Finally, it remains to lower the expected amortized time from O(tI (N ′ ) + tE (N ′ )) to O(tI (N ) +
tE (N )) where N is the number of elements actually present in the priority queue at the time
of the DecreaseKey. This is done using the standard global rebuilding technique: Initialize N0
to a constant. After N0 operations on the priority queue, all elements are extracted using the
ExtractMin operation. They are put on a list L. We then throw away the data structure and
initialize a new one from scratch. We then re-insert all elements of L in the new data structure and
set N0 to |L|/2. Since the number of elements in the priority queue is always within a constant
factor of the number of operations performed since the last rebuild, the expected amortized running
time is O(tI (N ) + tE (N )) as claimed. This trick also ensures that Insert and ExtractMin still run
in time O(tI (N )) and O(tE (N )) respectively.

23

