Tight Bounds for Single-Pass Streaming Complexity of the
Set Cover Problem
Sepehr Assadi∗

Sanjeev Khanna∗

Yang Li∗

arXiv:1603.05715v1 [] 17 Mar 2016

Abstract
We resolve the space complexity of single-pass streaming algorithms for approximating
√
the classic set cover problem. For finding an α-approximate set cover (for any α = o ( n))
using a single-pass streaming algorithm, we show that Θ(mn/α) space is both sufficient
and necessary (up to an O(log n) factor); here m denotes number of the sets and n denotes
size of the universe. This provides a strong negative answer to the open question posed by
Indyk et al. [17] regarding the possibility of having a single-pass algorithm with a small
approximation factor that uses sub-linear space.
We further study the problem of estimating the size of a minimum set cover (as opposed
to finding the actual sets), and establish that an additional factor of α saving in the space
is achievable in this case and that this is the best possible. In other words, we show that
Θ(mn/α2 ) space is both sufficient and necessary (up to logarithmic factors) for estimating
the size of a minimum set cover to within a factor of α. Our algorithm in fact works for
the more general problem of estimating the optimal value of a covering integer program.
On the other hand, our lower bound holds even for set cover instances where the sets are
presented in a random order.

∗ Department of Computer and Information Science, University of Pennsylvania. Supported in part by National
Science Foundation grants CCF-1116961, CCF-1552909, and IIS-1447470 and an Adobe research award.
Email: {sassadi,sanjeev,yangli2}@cis.upenn.edu.

1 Introduction
The set cover problem is a fundamental optimization problem with many applications in
computer science and related disciplines. The input is a universe [n] and a collection of
m subsets of [n], S = hS1 , . . . , Sm i, and the goal is to find a subset of S with the smallest
cardinality that covers [n], i.e., whose union is [n]; we call such a collection of sets a minimum
set cover and throughout the paper denote its cardinality by opt := opt (S).
The set cover problem can be formulated in the well-established streaming model [1, 23],
whereby the sets in S are presented one by one in a stream and the goal is to solve the
set cover problem using a space-efficient algorithm. The streaming setting for the set cover
problem has been studied in several recent work, including [7, 10, 12, 17, 27]. We refer the
interested reader to these references for many applications of the set cover problem in the
streaming model. In this paper, we focus on algorithms that make only one pass over the
stream (i.e., single-pass streaming algorithms), and our goal is to settle the space complexity
of single-pass streaming algorithms that approximate the set cover problem.
Two versions of the set cover problem are considered in this paper: (i ) computing a
minimum set cover, and (ii ) computing the size of a minimum set cover. Formally,
Definition 1 (α-approximation). An algorithm A is said to α-approximate the set cover problem
iff on every input instance S , A outputs a collection of (the indices of) at most α · opt sets that covers
[n], along with a certificate of covering which, for each element e ∈ [n], specifies the set used for
covering e. If A is a randomized algorithm, we require that the certificate corresponds to a valid set
cover w.p.1 at least 2/3.
We remark that the requirement of returning a certificate of covering is standard in the
literature (see, e.g., [7, 12]).
Definition 2 (α-estimation). An algorithm A is said to α-estimate the set cover problem iff on every
input instance S , A outputs an estimate for the cardinality of a minimum set cover in the range
[opt, α · opt ]. If A is a randomized algorithm, we require that:


Pr A(S) ∈ [opt, α · opt ] ≥ 2/3

1.1 Our Results
We resolve the space complexities
of both versions of the set cover problem. Specifically, we
√
show that for any α = o( n/ log n) and any m = poly(n),

• There is a deterministic single-pass streaming algorithm that α-approximates the set cover
e (mn/α) bits and moreover, any single-pass streaming algorithm
problem using space O
(possibly randomized) that α-approximates the set cover problem must use Ω(mn/α) bits
of space.
• There is a randomized single-pass streaming algorithm that α-estimates the set cover probe (mn/α2 ) bits and moreover, any single-pass streaming algorithm
lem using space O
e (mn/α2 ) bits of
(possibly randomized) that α-estimates the set cover problem must use Ω
space.

We should point out right away that in this paper, we are not concerned with poly-time
computability, though, our algorithms for set cover can be made computationally efficient for
any α ≥ log n by allowing an extra log n factor in the space requirement2.
1 Throughout,

we use w.p. and w.h.p. to abbreviate “with probability” and “with high probability”, respectively.
cover admits a classic log n-approximation algorithm [19, 28], and unless P = NP, there is no polynomial
time α-approximation for the set cover problem for α < (1 − ǫ) log n (for any constant ǫ > 0) [11, 13, 22].
2 Set

1

We establish our upper bound result for α-estimation for a much more general problem:
estimating the optimal value of a covering integer linear program (see Section 4 for a formal
definition). Moreover, the space lower bound for α-estimation (for the original set cover
problem) holds even if the sets are presented in a random order. We now describe each of
these two sets of results in more details.
Approximating Set Cover. There is a very simple deterministic α-approximation algorithm
e (mn/α) bits which we mention in Section 1.2 for
for the set cover problem using space O
completeness. Perhaps surprisingly, we establish that this simple algorithm is essentially the
e (mn/α)
best possible; any α-approximation algorithm for the set cover problem requires Ω
bits of space (see Theorem 1 for a formal statement).
Prior to our work, the best known lower bounds for single-pass
streams ruled out (3/2 −
√
ǫ)-approximation using o(mn) space [17] (see also [15]), o( n)-approximation in o(m) space [7,
12], and O(1)-approximation in o(mn) space [10] (only for deterministic algorithms); see Section 1.3 for more detail on different existing lower bounds. Note that these lower bound
results leave open the possibility of a single-pass randomized 3/2-approximation or even a
e (m)
deterministic O(log n)-approximation algorithm for the set cover problem using only O
space. Our result on the other hand, rules out the possibility of having any non-trivial tradeoff between the approximation factor and the space requirement, answering an open question
raised by Indyk et al. [17] in the strongest sense possible.
√
We should also point out that the √
bound of α = o( n/ log n) in our lower bound is tight
e (n)
up to an O(log n) factor since an O( n)-approximation is known to be achievable in O
space (essentially independent of m for m = poly(n)) [7, 12].
e (mn/α2 ) space algorithm for α-estimating the
Estimating Set Cover Size. We present an O
set cover problem, and in general any covering integer program (see Theorem 3 for a formal
statement). Our upper bound suggests that if one is only interested in α-estimating the size
of a minimum set cover (instead of knowing the actual sets), then an additional α factor
saving in the space (compare to the best possible α-approximation algorithm) is possible. To
the best of our knowledge, this is the first non-trivial gap between the space complexity of
α-approximation and α-estimation for the set cover problem.
e (mn/α2 ) space α-estimation algorithm
We further show that the space complexity of our O
for the set cover problem is essentially tight (up to logarithmic factors). In other words, any
e (mn/α2 ) space (see
α-estimation algorithm for set cover (possibly randomized) requires Ω
Theorem 4 for a formal statement).
There are examples of classic optimization problems in the streaming literature for which
size estimation seems to be distinctly easier in the random arrival streams3 compare to the
adversarial streams (see, e.g., [20]). However, we show that this is not the case for the set
e (mn/α2 ) for α-estimation continues to hold even for
cover problem, i.e., the lower bound of Ω
random arrival streams.
We note in passing two other results also: (i ) our bounds for α-approximation and αestimation also prove tight bounds on the one-way communication complexity of the two-player
communication model of the set cover problem (see Theorem 2 and Theorem 5), previously
studied in [7, 10, 24]; (ii ) the use of randomization in our α-estimation algorithm is inevitable:
any deterministic α-estimation algorithm for the set cover requires Ω(mn/α) bits of space (see
Theorem 6).
3 In random arrival streams, the input (in our case, the collection of sets) is randomly permuted before being
presented to the algorithm

2

1.2 Our Techniques
e (mn/α) bits of space can be simply achieved
Upper bounds. An α-approximation using O
as follows. Merge (i.e., take the union of) every α sets in the stream into a single set; at the
end of the stream, solve the set cover problem over the merged sets. To recover a certificate
of covering, we also record for each element e in each merged set, any set in the merge that
covers e. It is an easy exercise to verify that this algorithm indeed achieves an α-approximation
e (mn/α) bits.
and can be implemented in space O
2
e
Our O(mn/α )-space α-estimation algorithm is more involved and in fact works for any
covering integer program (henceforth, a covering ILP for short). We follow the line of work
in [10] and [17] by performing “dimensionality reduction” over the sets (in our case, columns
of the constraint matrix A) and storing their projection over a randomly sampled subset
of the universe (here, constraints) during the stream. However, the goal of our constraint
sampling approach is entirely different from the ones in [10,17]. The element sampling approach
of [10, 17] aims to find a “small” cover of the sampled universe which also covers the vast
majority of the elements in the original universe. This allows the algorithm to find a small set
cover of the sampled universe in one pass while reducing the number of remaining uncovered
elements for the next pass; hence, applying this approach repeatedly over multiple passes on
the input allows one to obtain a complete cover.
On the other hand, the goal of our constraint sampling approach is to create a smaller
instance of set cover (in general, covering ILP) with the property that the minimum set cover
size of the sampled instance is a “proxy” for the minimum set cover size of the original
instance. We crucially use the fact that the algorithm does not need to identify the actual
cover and hence it can estimate the size of the solution based on the optimum set cover size
in the sampled universe.
At the core of our approach is a simple yet very general lemma, referred to as the constraint
sampling lemma (Lemma 4.1) which may be of independent interest. Informally, this lemma
states that for any covering ILP instance I , the optimal value of a sub-sampled instance IR ,
obtained by picking roughly 1/α fraction of the constraints uniformly at random from I , is
an α estimator of the optimum value of I whenever no constraint is “too hard” to satisfy.
Nevertheless, the constraint sampling is not enough for reducing the space to meet the
e (mn/α2 ) bound (see Theorem 3). Hence, we combine it with a pruning step, similar
desired O
to the “set filtering” step of [17] for (unweighted) set cover (see also “GreedyPass” algorithm
of [7]) to sparsify the columns in the input matrix A before performing the sampling. We
point out that as the variables in I can have different weights in the objective function (e.g.
for weighted set cover), our pruning step needs to be sensitive to the weights.
Lower bounds. As is typical in the streaming literature, our lower bounds are obtained by
establishing communication complexity lower bounds; in particular, in the one-way two-player
communication model. To prove these bounds, we use the information complexity paradigm,
which allows one to reduce the problem, via a direct sum type argument, to multiple instances
of a simpler problem. For our lower bound for α-estimation, this simpler problem turned out
to be a variant of the well-known Set Disjointness problem. However, for the lower bound of
α-approximation algorithms, we introduce and analyze a new intermediate problem, called
the Trap problem.
The Trap problem is a non-boolean problem defined as follows: Alice is given a set S, Bob
is given a set E such that all elements of E belong to S except for a special element e∗ , and
the goal of the players is to “trap” this special element, i.e., to find a small subset of E which
contains e∗ . For our purpose, Bob only needs to trap e∗ in a set of cardinality | E| /2. To prove
a lower bound for the Trap problem, we design a novel reduction from the well-known Index
problem, which requires Alice and Bob to use the protocol for the Trap problem over non-

3

legal inputs (i.e., the ones for which the Trap problem is not well-defined), while ensuring
that they are not being “fooled” by the output of the Trap protocol over these inputs.
To prove our lower bound for α-estimation in random arrival streams, we follow the
approach of [5] in proving the communication complexity lower bounds when the input data
is randomly allocated between the players (as opposed to adversarial partitions). However, the
distributions and the problem considered in this paper are different from the ones in [5].

1.3 Related Work
Communication complexity of the set cover problem was first studied by Nisan [24]. Among
other things, Nisan showed that the two-player communication complexity of ( 21 − ǫ) log nestimating the set cover is Ω(m). In particular, this implies that any constant-pass streaming
algorithm that ( 12 − ǫ) log n-estimates the set cover must use Ω(m) bits of space.
Saha and Getoor [27] initiated the study of set cover in the semi-streaming model [14]
e (n) space,
where the sets are arriving in a stream and the algorithms are required to use O
and obtained an O(log n)-approximation via an O(log n)-pass algorithm that uses O(n log n)
space. A similar performance was also achieved by [8] in the context of “disk friendly”
algorithms. As designed, the algorithm of [8] achieves (1 + β ln n)-approximation by making
O(logβ n) passes over the stream using O(n log n) space.
The single-pass semi-streaming setting for set√cover was initially and throughly studied by
e (n) space (which
Emek and Rosén [12]. They provided an O( n)-approximation using O
also extends to the weighted set cover problem) and a lower bound that states that no semie (n) space) that O(n1/2−ǫ )-estimates set
streaming algorithm (i.e., an algorithm using only O
cover exists. Recently, Chakrabarti and Wirth [7] generalized the space bounds in [12] to multipass algorithms, providing an almost complete understanding of the pass/approximation
tradeoff for semi-streaming algorithms. In particular, they developed a deterministic pe (n) space and prove that any p-pass
pass ( p + 1) · n1/( p+1) -approximation algorithm in O
1/
(
p
+
1
)
2
n
/(c · ( p + 1) )-estimation algorithm requires Ω(nc /p3 ) space for some constant c√> 1
(m in their “hard instances” is Θ(ncp )). This, in particular, implies that any single-pass o( n)estimation algorithm requires Ω(m) space.
Demaine et al. [10] studied the trade-off between the number of passes, the approximation
ratio, and the space requirement of general streaming algorithms (i.e., not necessarily semistreaming) for the set cover problem and developed an algorithm that for any δ = Ω(1/ log n),
e (mnδ )
makes O(41/δ ) passes over the stream and achieves an O(41/δ ρ)-approximation using O
space; here ρ is the approximation factor of the off-line algorithm for solving the set cover
problem. The authors further showed that any constant-pass deterministic O(1)-estimation algorithm for the set cover requires Ω(mn) space. Very recently, Indyk et al. [17] (see also [15])
made a significant improvement on the trade-off achieved by [10]: they presented an algorithm that for any δ > 0, makes O(1/δ) passes over the stream and achieves an O(ρ/δ)e (mnδ ) space. The authors also established two lower bounds: for
approximation using O
multi-pass algorithms, any algorithm that computes an optimal set cover solution while mak1
e (mnδ ) space. More relevant to our paper, they also showed
− 1) passes must use Ω
ing only ( 2δ
that any single-pass streaming algorithm (possibly randomized) that can distinguish between
the instances with set cover size of 2 and 3 w.h.p., must use Ω(mn) bits.
Organization. We introduce in Section 2 some preliminaries needed for the rest of the paper.
In Section 3, we present our Ω(mn/α) space lower bound for computing an α-approximate
set cover in a single-pass. In Section 4, we present a single-pass streaming algorithm for
e (mn/α2 ) upper
estimating the optimal value of a covering integer program and prove an O
bound on the space complexity of α-estimating the (weighted) set cover problem. In Section 5,
we present our Ω(mn/α2 ) space lower bound for α-estimating set cover in a single-pass.
4

Finally, Section 6 contains our Ω(mn/α) space lower bound for deterministic α-estimation
algorithms.

2 Preliminaries
Notation. We use bold face letters to represent random variables. For any random variable X, supp( X ) denotes its support set. We define | X | := log |supp( X )|. For any kdimensional tuple X = ( X1 , . . . , Xk ) and any i ∈ [k], we define X <i := ( X1 , . . . , Xi−1 ), and
X −i := ( X1 , . . . , Xi−1 , Xi+1 , . . . , Xk ). The notation “X ∈ R U” indicates that X is chosen uniformly at random from a set U. Finally, we use upper case letters (e.g. M) to represent
matrices and lower case letter (e.g. v) to represent vectors.
Concentration Bounds. We use an extension of the Chernoff-Hoeffding bound for negatively
correlated random variables. Random variables X1 , . . . , Xn are negatively correlated if for
every set S ⊆ [n], Pr (∧i∈S Xi = 1) ≤ ∏i∈S Pr ( Xi = 1). It was first proved in [25] that the
Chernoff-Hoeffding bound continues to hold for the case of random variables that satisfy this
generalized version of negative correlation (see also [16]).

2.1 Tools from Information Theory
We briefly review some basic concepts from information theory needed for establishing our
lower bounds. For a broader introduction to the field, we refer the reader to the excellent text
by Cover and Thomas [9].
In the following, we denote the Shannon Entropy of a random variable A by H ( A) and
the mutual information of two random variables A and B by I ( A; B) = H ( A) − H ( A | B) =
H ( B) − H ( B | A). If the distribution D of the random variables is not clear from the context,
we use HD ( A) (resp. ID ( A; B)). We use H2 to denote the binary entropy function where for
any real number 0 < δ < 1, H2 (δ) = δ log 1δ + (1 − δ) log 1−1 δ .
We use the following basic properties of entropy and mutual information (proofs can be
found in [9], Chapter 2).
Claim 2.1. Let A, B, and C be three random variables.
1. 0 ≤ H ( A) ≤ | A|. H ( A) = | A| iff A is uniformly distributed over its support.
2. I ( A; B) ≥ 0. The equality holds iff A and B are independent.
3. Conditioning on a random variable reduces entropy: H ( A | B, C ) ≤ H ( A | B). The
equality holds iff A and C are independent conditioned on B.
4. Subadditivity of entropy: H ( A, B | C ) ≤ H ( A | C ) + H ( B | C ).
5. The chain rule for mutual information: I ( A, B; C ) = I ( A; C ) + I ( B; C | A).
6. For any event E independent of A and B, H ( A | B, E) = H ( A | B).
7. For any event E independent of A, B and C, I ( A; B | C, E) = I ( A; B | C ).
The following claim (Fano’s inequality) states that if a random variable A can be used
to estimate the value of another random variable B, then A should “consume” most of the
entropy of B.
Claim 2.2 (Fano’s inequality). For any binary random variable B and any (possibly randomized)
function f that predicts B based on A, if Pr(f(A)6= B) = δ, then H ( B | A) ≤ H2 (δ).
5

We also use the following simple claim, which states that conditioning on independent
random variables can only increase the mutual information.
Claim 2.3. For any random variables A, B, C, and D, if A and D are independent conditioned on C,
then I ( A; B | C ) ≤ I ( A; B | C, D ).
Proof. Since A and D are independent conditioned on C, by Claim 2.1-(3), H ( A | C ) =
H ( A | C, D ) and H ( A | C, B) ≥ H ( A | C, B, D ). We have,
I ( A; B | C ) = H ( A | C ) − H ( A | C, B) = H ( A | C, D ) − H ( A | C, B)

≤ H ( A | C, D ) − H ( A | C, B, D ) = I ( A; B | C, D )

2.2 Communication Complexity and Information Complexity
Communication complexity and information complexity play an important role in our lower
bound proofs. We now provide necessary definitions for completeness.
Communication complexity. Our lowers bounds for single-pass streaming algorithms are
established through communication complexity lower bounds. Here, we briefly provide some
context necessary for our purpose; for a more detailed treatment of communication complexity, we refer the reader to the excellent text by Kushilevitz and Nisan [21].
We focus on the two-player one-way communication model. Let P be a relation with domain
X × Y × Z . Alice receives an input X ∈ X and Bob receives Y ∈ Y , where ( X, Y ) are chosen
from a joint distribution D over X × Y . In addition to private randomness, the players also
have an access to a shared public tape of random bits R. Alice sends a single message M ( X, R)
and Bob needs to output an answer Z := Z ( M ( X, R), Y, R) such that ( X, Y, Z ) ∈ P.
We use Π to denote a protocol used by the players. Unless specified otherwise, we always
assume that the protocol Π can be randomized (using both public and private randomness),
even against a prior distribution D of inputs. For any 0 < δ < 1, we say Π is a δ-error protocol
for P over a distribution D , if the probability that for an input ( X, Y ), Bob outputs some Z
where ( X, Y, Z ) ∈
/ P is at most δ (the probability is taken over the randomness of both the
distribution and the protocol).
Definition 3. The communication cost of a protocol Π for a problem P on an input distribution D ,
denoted by kΠk, is the worst-case size of the message sent from Alice to Bob in the protocol Π, when
the inputs are chosen from the distribution D .
The communication complexity CCδD ( P) of a problem P with respect to a distribution D is the
minimum communication cost of a δ-error protocol Π over D .
Information complexity. There are several possible definitions of information complexity
of a communication problem that have been considered depending on the application (see,
e.g., [2–4, 6]). Our definition is tuned specifically for one-way protocols, similar in the spirit
of [3] (see also [18]).
Definition 4. Consider an input distribution D and a protocol Π (for some problem P). Let X be
the random variable for the input of Alice drawn from D , and let Π := Π( X ) be the random variable
denoting the message sent from Alice to Bob concatenated with the public randomness R used by Π.
The information cost ICostD (Π) of a one-way protocol Π with respect to D is ID (Π; X ).
The information complexity ICδD ( P) of P with respect to a distribution D is the minimum ICostD (Π)
taken over all one-way δ-error protocols Π for P over D .
6

Note that any public coin protocol is a distribution over private coins protocols, run by
first using public randomness to sample a random string R = R and then running the corresponding private coin protocol Π R . We also use Π R to denote the random variable of the
message sent from Alice to Bob, assuming that the public randomness is R = R. We have the
following well-known claim.
Claim 2.4. For any distribution
h D and any protocol
i Π, let R denote the public randomness used in
Π; then, ICostD (Π) = ER∼ R ID (Π R ; X | R = R) .
Proof. Let Π = ( M, R), where M denotes the message sent by Alice and R is the public
randomness. We have,
ICostD (Π) = I (Π; X ) = I ( M, R; X ) = I ( R; X ) + I ( M; X | R)

= E

R∼ R

h

(the chain rule for mutual information, Claim 2.1-(5))
i
ID (Π R ; X | R = R)

(M = Π R whenever R = R and I ( R; X ) = 0 by Claim 2.1-(2))

The following well-known proposition (see, e.g., [6]) relates communication complexity
and information complexity.
Proposition 2.5. For every 0 < δ < 1 and every distribution D : CCδD ( P) ≥ ICδD ( P).
Proof. Let Π be a protocol with the minimum communication complexity for P on D and R
denotes the public randomness of Π; using Claim 2.4, we can write,
h
i
h
i
ICδD ( P) = E ID (Π R ; X | R = R) ≤ E HD (Π R | R = R)
R∼ R
R∼ R
h
i
R
δ
≤ E
Π
≤ kΠk = CCD ( P)
R∼ R

3 An Ω(mn/α)-Space Lower bound for α-Approximate Set Cover
In this section, we prove that the simple α-approximation algorithm described in Section 1.2
is in fact optimal in terms of the space requirement. Formally,
√

Theorem 1. For any α = o( lognn ) and m = poly(n), any randomized single-pass streaming algorithm that α-approximates the set cover problem with probability at least 2/3 requires Ω(mn/α) bits
of space.
√

Fix a (sufficiently large) value for n, m = poly(n) (also m = Ω(α log n)), and α = o( lognn );
throughout this section, SetCoverapx refers to the problem of α-approximating the set cover
problem for instances with m + 1 sets4 defined over the universe [n] in the one-way communication model, whereby the sets are partitioned between Alice and Bob.
4 To

simplify the exposition, we use m + 1 instead of m as the number of sets.

7

Overview. We design a hard input distribution Dapx for SetCoverapx , whereby Alice is provided with a collection of m sets S1 , . . . , Sm , each of size (roughly) n/α and Bob is given a
single set T of size (roughly) n − 2α. The input to the players are correlated such that there exists a set Si∗ in Alice’s collection (i ∗ is unknown to Alice), such that Si∗ ∪ T covers all elements
in [n] except for a single special element. This in particular ensures that the optimal set cover
size in this distribution is at most 3 w.h.p.
On the other hand, we “hide” this special element among the 2α elements in T in a way
that if Bob does not have (essentially) full information about Alice’s collection, he cannot even
identify a set of α elements from T that contain this special element (w.p strictly more than
half). This implies that in order for Bob to be sure that he returns a valid set cover, he should
additionally cover a majority of T with sets other than Si∗ . We design the distribution in a way
that the sets in Alice’s collection are “far” from each other and hence Bob is forced to use
a distinct set for (roughly) each element in T that he needs to cover with sets other than Si∗ .
This implies that Bob needs to output a set cover of size α (i.e., an (α/3)-approximation) to
ensure that every element in [n] is covered.

3.1 A Hard Input Distribution for SetCoverapx
Consider the following distribution.
Distribution Dapx . A hard input distribution for SetCoverapx .
Notation. Let F be the collection of all subsets of [n] with cardinality

n
10α ,

and ℓ := 2α log m.

• Alice. The input of Alice is a collection of m sets S = (S1 , . . . , Sm ), where for any
i ∈ [m], Si is a set chosen independently and uniformly at random from F .
• Bob. Pick an i∗ ∈ [m] (called the special index) uniformly at random; the input to Bob
is a set T = [n] \ E, where E is chosen uniformly at random from all subsets of [n]
with | E| = ℓ and | E \ Si∗ | = 1.a
a Since

√
α = o ( n/ log n ) and m = poly(n ), the size of E is strictly smaller than the size of Si∗ .

The claims below summarize some useful properties of the distribution Dapx .

Claim 3.1. For any instance (S , T ) ∼ Dapx , with probability 1 − o(1), opt (S , T ) ≤ 3.
∗

Proof. Let e∗ denote the element in E \ Si∗ . S −i contains m − 1 random subsets of [n] of
∗
size n/10α, drawn independent of the choice of e∗ . Therefore, each set in S −i covers e∗ with
probability 1/10α. The probability that none of these m − 1 sets covers e∗ is at most

(1 − 1/10α)m−1 ≤ (1 − 1/10α)Ω(α log n) ≤ exp(−Ω(α log n)/10α) = o(1)
∗

Hence, with probability 1 − o(1), there is at least one set S ∈ S −i that covers e∗ . Now, it is
straightforward to verify that (Si∗ , T, S) form a valid set cover.
∗

Lemma 3.2. With probability 1 − o(1), no collection of 3α sets from S −i covers more than ℓ/2
elements of E.
∗

Proof. Recall that the sets in S −i and the set E are chosen independent of each other. For
∗
each set S ∈ S −i and for each element e ∈ E, we define an indicator binary random variable
Xe , where Xe = 1 iff e ∈ S. Let X := ∑e Xe , which is the number of elements in E covered by
S. We have,
log m
|E|
=
E [ X ] = ∑ E[ X e ] =
10α
5
e
8

Moreover, the variables Xe are negatively correlated since for any set S′ ⊆ E,
Pr

^

e∈S′

Xe = 1

!

=

(

n −|S ′ |

n
′
10α −|S |

(

n

n
10α

)

)



n
n
· 10α
− 1 . . . 10α
− |S′ | + 1
=
( n ) · ( n − 1) . . . ( n − | S ′ | + 1)

 ′
1 |S |
= ∏ Pr ( Xe = 1)
≤
10α
e∈S′
n
10α



Hence, by the extended Chernoff bound (see Section 2),


log m
1
Pr X ≥
= o( )
3
m
∗

Therefore, using union bound over all m − 1 sets in S −i , with probability 1 − o(1), no set in
∗
S −i covers more than log m/3 elements in E, which implies that any collection of 3α sets can
only cover up to 3α · log m/3 = ℓ/2 elements in E.

3.2 The Lower Bound for the Distribution Dapx
In order to prove our lower bound for SetCoverapx on Dapx , we define an intermediate communication problem which we call the Trap problem.
Problem 1 (Trap problem). Alice is given a set S ⊆ [n] and Bob is given a set E ⊆ [n] such that
E \ S = {e∗ }; Bob needs to output a set L ⊆ E with | L| ≤ | E| /2 such that e∗ ∈ L.
In the following, we use Trap to refer to the trap problem with | S| = n/10α and | E| = ℓ =
2α log m (notice the similarity to the parameters in Dapx ). We define the following distribution
DTrap for Trap. Alice is given a set S ∈ R F (recall that F is the collection of all subsets of [n]
of size n/10α) and Bob is given a set E chosen uniformly at random from all sets that satisfy
| E \ S| = 1 and |E| = 2α log m. We first use a direct sum style argument to prove that under
the distributions Dapx and DTrap , information complexity of solving SetCoverapx is essentially
equivalent to solving m copies of Trap. Formally,
δ + o ( 1)

Lemma 3.3. For any constant δ < 1/2, ICδDapx (SetCoverapx ) ≥ m · ICDTrap (Trap).
Proof. Let ΠSC be a δ-error protocol for SetCoverapx ; we design a δ′ -error protocol ΠTrap for
solving Trap over DTrap with parameter δ′ = δ + o(1) such that the information cost of ΠTrap
on DTrap is at most m1 · ICostDapx (ΠSC ). The protocol ΠTrap is as follows.
Protocol ΠTrap . The protocol for solving Trap using a protocol ΠSC for SetCoverapx .
Input: An instance (S, E) ∼ DTrap . Output: A set L with | L| ≤ | E| /2, such that e∗ ∈ L.
1. Using public randomness, the players sample an index i∗ ∈ [m] uniformly at random.
2. Alice creates a tuple S = (S1 , . . . , Sm ) by assigning Si∗ = S and sampling each remaining set uniformly at random from F using private randomness. Bob creates a set
T := E.
3. The players run the protocol ΠSC over the input (S , T ).
4. Bob computes the set L of all elements in E = T whose certificate (i.e., the set used to
cover them) is not Si∗ , and outputs L.

9

We first argue the correctness of ΠTrap and then bound its information cost. To argue the
correctness, notice that the distribution of instances of SetCoverapx constructed in the reduction
is exactly Dapx . Consequently, it follows from Claim 3.1 that, with probability 1 − o(1), any
α-approximate set cover can have at most 3α sets. Let Sb be the set cover computed by Bob
minus the sets Si∗ and T. As e∗ ∈ E = T and moreover is not in Si∗ , it follows that e∗ should
be covered by some set in Sb. This means that the set L that is output by Bob contains e∗ .
Moreover, by Lemma 3.2, the number of elements in E covered by the sets in Sb is at most ℓ/2
w.p. 1 − o(1). Hence, | L| ≤ ℓ/2 = | E| /2. This implies that:




Pr ΠTrap errs ≤ Pr ΠSC errs + o(1) ≤ δ + o(1)
DTrap

Dapx

We now bound the information cost of ΠTrap . Let I be the random variable for the choice
of ∈ [m] in the protocol ΠTrap (which is uniform in [m]). Using Claim 2.4, we have,
i∗

i



1 m
i
;S | I = i =
IDTrap ΠTrap
· ∑ IDTrap ΠSC ; Si | I = i
m i=1
i∼ I




m
1
1 m
= · ∑ IDapx ΠSC ; Si | I = i = · ∑ IDapx ΠSC ; Si
m i=1
m i=1

ICostDTrap (ΠTrap ) = E

h

where the last two equalities hold since (i ) the joint distribution of ΠSC and Si conditioned
on I = i under DTrap is equivalent to the one under Dapx , and (ii ) the random variables ΠSC
and Si are independent of the event I = i (by the definition of Dapx ) and hence we can “drop”
the conditioning on this event (by Claim 2.1-(7)).
We can further derive,
ICostDTrap (ΠTrap ) =





1 m
1 m
· ∑ IDapx ΠSC ; Si ≤ · ∑ IDapx ΠSC ; Si | S <i
m i=1
m i=1

The inequality holds since Si and S <i are independent and conditioning on independent
variables can only increase the mutual information (i.e., Claim 2.3). Finally,
ICostDTrap (ΠTrap ) ≤





1 m
1
1
· ∑ IDapx ΠSC ; Si | S <i = · IDapx ΠSC ; S = · ICostDapx (ΠSC )
m i=1
m
m

where the first equality is by the chain rule for mutual information (see Claim 2.1-(5)).
Having established Lemma 3.3, our task now is to lower bound the information complexity of Trap over the distribution DTrap . We prove this lower bound using a novel reduction
from the well-known Index problem, denoted by Indexnk . In Indexnk over the distribution DIndex ,
Alice is given a set A ⊆ [n] of size k chosen uniformly at random and Bob is given an element
a such that w.p. 1/2 a ∈ R A and w.p. 1/2 a ∈ R [n] \ A; Bob needs to determine whether
a ∈ A (the YES case) or not (the NO case).
We remark that similar distributions for Indexnk have been previously studied in the literature (see, e.g., [26], Section 3.3). For the sake of completeness, we provide a self-contained
proof of the following lemma in Appendix A.
′

Lemma 3.4. For any k < n/2, and any constant δ′ < 1/2, ICδDIndex (Indexnk ) = Ω(k).
Using Lemma 3.4, we prove the following lemma, which is the key part of the proof.
Lemma 3.5. For any constant δ < 1/2, ICδDTrap (Trap) = Ω(n/α).

10

Proof. Let k = n/10α; we design a δ′ -error protocol ΠIndex for Indexnk using any δ-error
protocol ΠTrap (over DTrap ) as a subroutine, for some constant δ′ < 1/2.
Protocol ΠIndex . The protocol for reducing Indexnk to Trap.
Input: An instance ( A, a) ∼ DIndex . Output: YES if a ∈ A and NO otherwise.
1. Alice picks a set B ⊆ A with | B| = ℓ − 1 uniformly at random using private randomness.
2. To invoke the protocol ΠTrap , Alice creates a set S := A and sends the message
ΠTrap (S), along with the set B to Bob.
3. If a ∈ B, Bob outputs YES and terminates the protocol.
4. Otherwise, Bob constructs a set E = B ∪ { a} and computes L := ΠTrap (S, E) using the
message received from Alice.
5. If a ∈ L, Bob outputs NO, and otherwise outputs YES.
We should note right away that the distribution of instances for Trap defined in the previous reduction does not match DTrap . Therefore, we need a more careful argument to establish
the correctness of the reduction.
We prove this lemma in two claims; the first claim establishes the correctness of the reduction and the second one proves an upper bound on the information cost of ΠIndex based
on the information cost of ΠTrap .
Claim 3.6. ΠIndex is a δ′ -error protocol for Indexnk over DIndex for the parameter k = n/10α and a
constant δ′ < 1/2.
Y
Proof. Let R denote the private coins used by Alice to construct the set B. Also, define DIndex
N
(resp. DIndex ) as the distribution of YES instances (resp. NO instances) of DIndex . We have,

Pr

DIndex ,R




 1



1
ΠIndex errs + · Pr
ΠIndex errs
ΠIndex errs = · Pr
Y
N
2 DIndex
2 DIndex
,R
,R

(1)

Note that we do not consider the randomness of the protocol ΠTrap (used in construction of
ΠIndex ) as it is independent of the randomness of the distribution DIndex and the private coins
R. We now bound each term in Equation (1) separately. We first start with the easier case
which is the second term.
The distribution of instances (S, E) for Trap created in the reduction by the choice of
N
and the randomness of R, is the same as the distribution DTrap . Moreover, in
( A, a) ∼ DIndex
this case, the output of ΠIndex would be wrong iff a ∈ E \ S (corresponding to the element e∗
in Trap) does not belong to the set L output by ΠTrap . Hence,




(2)
ΠIndex errs = Pr ΠTrap errs ≤ δ
Pr
N
,R
DIndex

DTrap

Y
We now bound the first term in Equation (1). Note that when ( A, a) ∼ DIndex
, there is a
small chance that ΠIndex is “lucky" and a belongs to the set B (see Line (3) of the protocol).
Let this event be E . Conditioned on E , Bob outputs the correct answer with probability 1;
however note that probability of E happening is only o(1). Now suppose E does not happen.
Y
(and
In this case, the distribution of instances (S, E) created by the choice of ( A, a) ∼ DIndex
randomness of R) does not match the distribution DTrap . However, we have the following

11

important property: Given that (S, E) is the instance of Trap created by choosing ( A, a) from
Y
and sampling ℓ − 1 random elements of A (using R), the element a is uniform over the
DIndex
set E. In other words, knowing (S, E) does not reveal any information about the element a.
Note that since (S, E) is not chosen according to the distribution DTrap (actually it is not
even a “legal” input for Trap), it is possible that ΠTrap terminates, outputs a non-valid set, or
outputs a set L ⊆ E. Unless L ⊆ E (and satisfies the cardinality constraint), Bob is always able
to determine that ΠTrap is not functioning correctly and hence outputs YES (and errs with
probability at most δ < 1/2). However, if L ⊆ E, Bob would not know whether the input to
ΠTrap is legal or not. In the following, we explicitly analyze this case.
In this case, L is a subset of E chosen by the (inner) randomness of ΠTrap for a fixed S
and E and moreover | L| ≤ | E| /2 (by definition of Trap). The probability that ΠIndex errs in
this case is exactly equal to the probability that a ∈ L. However, as stated before, for a fixed
(S, E), the choice of L is independent of the choice of a and moreover, a is uniform over E;
hence a ∈ L happens with probability at most 1/2. Formally, (here, RTrap denotes the inner
randomness of ΠTrap )


a ∈ L = ΠTrap (S, E) | E
Pr (ΠIndex errs | E ) = Pr
Y
,R
DIndex

Y
,R
DIndex

=

E

E

( S,E )∼( S,E )|E RTrap ∼ RTrap

h

Pr

Y
DIndex
,R



a ∈ L | S = S, E = E, RTrap = RTrap , E

i

(L = ΠTrap (S, E) is a fixed set conditioned on (S, E, RTrap ))
h | L| i
E
=
E
( S,E )∼( S,E )|E RTrap ∼ RTrap | E |
(a is uniform on E conditioned on (S, E, RTrap ) and E )

Hence, we have, PrDY ,R (ΠIndex errs | E ) ≤ 12 , since by definition, for any output set L,
Index
| L| ≤ | E| /2.
As stated earlier, whenever E happens, ΠIndex makes no error; hence,
Pr (ΠIndex errs) =

Y
,R
DIndex

Pr (E ) ·

Y
,R
DIndex

Pr (ΠIndex errs | E ) ≤

Y
,R
DIndex

1 − o ( 1)
2

(3)

Finally, by plugging the bounds in Equations (2,3) in Equation (1) and assuming δ is bounded
away from 1/2, we have,
Pr (ΠIndex errs) ≤

DIndex ,R

1 1 − o ( 1) 1
1 − o ( 1) δ
1
·
+ ·δ =
+ ≤ −ǫ
2
2
2
4
2
2

for some constant ǫ bounded away from 0.
We now bound the information cost of ΠIndex under DIndex .
Claim 3.7. ICostDIndex (ΠIndex ) ≤ ICostDTrap (ΠTrap ) + O(ℓ log n).
Proof. We have,




ICostDIndex (ΠIndex ) = IDIndex ΠIndex ( A); A


= IDIndex ΠTrap (S), B; A




= IDIndex ΠTrap (S); A + IDIndex B; A | ΠTrap (S)

≤ IDIndex



(the chain rule for mutual information, Claim 2.1-(5))



ΠTrap (S); A + HDIndex B | ΠTrap (S)
12



≤ IDIndex ΠTrap (S); A + O(ℓ log n) (| B| = O(ℓ log n) and Claim 2.1-(1))


(A = S as defined in ΠIndex )
= IDIndex ΠTrap (S); S + O(ℓ log n)


= IDTrap ΠTrap (S); S + O(ℓ log n)

(the joint distribution of (ΠTrap (S), S) is identical under DIndex and DTrap )

= ICostDTrap (ΠTrap ) + O(ℓ log n)

The lower bound now follows from Claims 3.6 and 3.7, and√
Lemma 3.4 for the parameters
n
and δ′ < 1/2, and using the fact that α = o( n/ log n), ℓ = 2α log m, and
k = | S| = 10α
m = poly(n), and hence Ω(n/α) = ω (ℓ log n).
√

To conclude, by Lemma 3.3 and Lemma 3.5, for any set of parameters δ < 1/2, α = o( lognn ),
and m = poly(n),


ICδDapx (SetCoverapx ) ≥ m · Ω(n/α) = Ω(mn/α)

Since the information complexity is a lower bound on the communication complexity (Proposition 2.5), we have,
√

Theorem 2. For any constant δ < 1/2, α = o( lognn ), and m = poly(n),
CCδDapx (SetCoverapx ) = Ω(mn/α)
Finally, since one-way communication complexity is also a lower bound on the space complexity of single-pass streaming algorithms, we obtain Theorem 1 as a corollary of Theorem 2.

e (mn/α2 )-Space Upper Bound for α-Estimation
4 An O

In this section, we show that if we are only interested in estimating the size of a minimum set
cover (instead of finding the actual sets), we can bypass the Ω(mn/α) lower bound established
in Section 3. In fact, we prove this upper bound for the more general problem of estimating
the optimal solution of a covering integer program (henceforth, covering ILP) in the streaming
setting.
A covering ILP can be formally defined as follows.
min c · x s.t. Ax ≥ b

where A is a matrix with dimension n × m, b is a vector of dimension n, c is a vector of
dimension m, and x is an m-dimensional vector of non-negative integer variables. Moreover,
all coefficients in A, b, and c are also non-negative integers. We denote this linear program
by ILPCover ( A, b, c). We use amax , bmax , and cmax , to denote the largest entry of, respectively,
the matrix A, the vector b, and the vector c. Finally, we define the optimal value of the I :=
ILPCover ( A, b, c) as c · x∗ where x∗ is the optimal solution to I , and denote it by opt := opt (I).
We consider the following streaming setting for covering ILPs. The input to a streaming
algorithm for an instance I := ILPCover ( A, b, c) is the n-dimensional vector b, and a stream of
the m columns of A presented one by one, where the i-th column of A, Ai , is presented along
with the i-th entry of c, denoted by ci (we will refer to ci as the weight of the i-th column).
It is easy to see that this streaming setting for covering ILPs captures, as special cases, the
set cover problem, the weighted set cover problem, and the set multi-cover problem. We prove
the following theorem for α-estimating the optimal value of a covering ILPs in the streaming
setting.
13

Theorem 3. There is a randomized algorithm that given a parameter α ≥ 1, for any instance
I := ILPCover ( A, b, c) with poly(n)-bounded entries, makes a single pass over a stream of columns
of A (presented in an arbitrary order),
and outputs an α-estimation to opt (I) w.h.p. using space

e (mn/α2 ) · bmax + m + nbmax bits.
O
√
In particular, for the weighted set cover problem with poly(n) bounded weights and α ≤ n,
e (mn/α2 + n).5
the space complexity of this algorithm is O

To prove Theorem 3, we design a general approach based on sampling constraints of a
covering ILP instance. The goal is to show that if we sample (roughly) 1/α fraction of the
constraints from an instance I := ILPCover ( A, b, c), then the optimum value of the resulting
covering ILP, denoted by IR , is a good estimator of opt (I). Note that in general, this may not
be the case; simply consider a weighted set cover instance that contains an element e which
is only covered by a singleton set of weight W (for W ≫ m) and all the remaining sets are of
weight 1 only. Clearly, opt (IR ) ≪ opt (I) as long as e is not sampled in IR , which happens
w.p. 1 − 1/α.
To circumvent this issue, we define a notion of cost for covering ILPs which, informally, is
the minimum value of the objective function if the goal is to only satisfy a single constraint
(in the above example, the cost of that weighted set cover instance is W). This allows us to
bound the loss incurred in the process of estimation by sampling based on the cost of the
covering ILP.
Constraint sampling alone can only reduce the space requirement by a factor of α, which
is not enough to meet the bounds given in Theorem 3. Hence, we combine it with a pruning
step to sparsify the columns in A before performing the sampling. We should point out that
as columns are weighted, the pruning step needs to be sensitive to the weights.
In the rest of this section, we first introduce our constraint sampling lemma (Lemma 4.1)
and prove its correctness, and then provide our algorithm for Theorem 3.

4.1 Covering ILPs and Constraint Sampling Lemma
In this section, we provide a general result for estimating the optimal value of a Covering ILP
using a sampling based approach. For a vector v, we will use vi to denote the i-th dimension
of v. For a matrix A, we will use Ai to denote the i-th column of A, and use a j,i to denote
the entry of A at the i-th column and the j-th row (to match the notation with the set cover
problem, we use a j,i instead of the standard notation ai,j ).
For each constraint j ∈ [n] (i.e., the j-th constraint) of a covering ILP instance I :=
ILPCover ( A, b, c), we define the cost of the constraint j, denoted by Cost( j), as,
m

Cost( j) := min c · x s.t
x

∑ aj,i · xi ≥ bj

i=1

which is the minimum solution value of the objective function for satisfying the constraint j.
Furthermore, the cost of I , denoted by Cost(I), is defined to be
Cost(I) := max Cost( j)
j∈[n ]

Clearly, Cost(I) is a lower bound on opt (I).
Constraint Sampling. Given any instance of covering ILP I := ILPCover ( A, b, c), let IR be
a covering ILP instance ILPCover ( A, e
b, c) obtained by setting e
b j := b j with probability p, and
e
b j := 0 with probability 1 − p, for each dimension j ∈ [n] of b independently. Note that setting
5 Note

that Ω(n ) space is necessary to even determine whether or not a given instance is feasible.

14

e
b j := 0 in IR is equivalent to removing the j-th constraint from I , since all entries in I are
non-negative. Therefore, intuitively, IR is a covering ILP obtained by sampling (and keeping)
the constraints of I with a sampling rate of p.
We establish the following lemma which asserts that opt (IR ) is a good estimator of opt (I)
(under certain conditions). As opt (IR ) ≤ opt (I) trivially holds (removing constraints can
only decrease the optimal value), it suffices to give a lower bound on opt (IR ).
Lemma 4.1 (Constraint Sampling Lemma). Fix an α ≥ 32 ln n; for any covering ILP I with n
constraints, suppose IR is obtained from I by sampling each constraint with probability p := 4 lnα n ;
then

opt (I) 
3
Pr opt (IR ) + Cost(I) ≥
≥
8α
4
Proof. Suppose by contradiction that the lemma statement is false and throughout the proof
opt(I )
let I be any instance where w.p. at least 1/4, opt (IR ) + Cost(I) < 8α (we denote this
event by E1 (IR ), or shortly E1 ). We will show that in this case, I has a feasible solution with
a value smaller than opt (I). To continue, define E2 (IR ) (or E2 in short) as the event that
opt(I )
opt (IR ) < 8α . Note that whenever E1 happens, then E2 also happens, hence E2 happens
w.p. at least 1/4.
For the sake of analysis, suppose we repeat, for 32α times, the procedure of sampling
each constraint
of I independently with probability p, and obtain 32α covering ILP instances

S := IR1 , . . . , IR32α . Since E2 happens with probability at least 1/4 on each instance IR , the
expected number of times that E2 happens for instances in S is at least 8α > 12 ln n. Hence, by
the Chernoff bound, with probability at least 1 − 1/n, E2 happens on at least 4α of instances
in S. Let T ⊆ S be a set of 4α sampled instances for which E2 happens. In the following,
we show that if I has the property that Pr(E1 (I R )) ≥ 1/4, then w.p. at least 1 − 1/n, every
constraint in I appears in at least one of the instances in T. Since each of these 4α instances
opt(I )
admits a solution of value at most 8α (by the definition of E2 ), the “max” of their solutions,
i.e., the vector obtained by setting the i-th entry to be the largest value of xi among all these
opt(I )
opt(I )
solutions, gives a feasible solution to I with value at most 4α · 8α = 2 ; a contradiction.
We use “j ∈ IR ” to denote the event that the constraint j of I is sampled in IR , and we
need to show that w.h.p. for all j, there exists an instance IR ∈ T where j ∈ IR . We establish
the following claim.


Claim 4.2. For any j ∈ [n], Pr j ∈ IR | E2 (IR ) ≥ ln2αn .
Before proving Claim 4.2, we show how this claim would imply the lemma. By Claim 4.2,
for each of the 4α instances IR ∈ T, and for any j ∈ [n], the probability that the constraint
j is sampled in IR is at least ln2αn . Then, the probability that j is sampled in none of the 4α
instances of T is at most:

1
ln n 4α
≤ exp(−2 ln n) = 2
1−
2α
n

Hence, by union bound, w.p. at least 1 − 1/n, every constraint appears in at least one of the
instances in T, and this will complete the proof. It remains to prove Claim 4.2.

Proof of Claim 4.2. Fix any j ∈ [n]; by Bayes rule,




Pr E2 (IR ) | j ∈ IR · Pr ( j ∈ IR )


Pr j ∈ IR | E2 (IR ) =
Pr E2 (IR )
15



Since Pr E2 (IR ) ≤ 1 and Pr ( j ∈ IR ) = p =

4 ln n
α ,

we have,




 4 ln n
Pr j ∈ IR | E2 (IR ) ≥ Pr E2 (IR ) | j ∈ IR ·
α


and it suffices to establish a lower bound of 1/8 for Pr E2 (IR ) | j ∈ IR .

(4)

Consider the following probabilistic process (for a fixed j ∈ [n]): we first remove the
constraint j from I (w.p. 1) and then sample each of the remaining constraints of I w.p. p.
Let IR′ be an instance created by this process. We prove Pr (E2 (IR ) | j ∈ IR ) ≥ 1/8 in two
steps by first showing that the probability that E1 happens to IR′ (i.e., Pr (E1 (IR′ ))) is at least
1/8, and then use a coupling argument to prove that Pr (E2 (IR ) | j ∈ IR ) ≥ Pr (E1 (IR′ )).
We first show that Pr (E1 (IR′ )) (which by definition is the probability that opt (IR′ ) +
opt(I )
Cost(I) ≤ 16α ) is at least 1/8. To see this, note that the probability that E1 happens to
IR′ is equal to the probability that E1 happens to IR conditioned on j not being sampled (i.e.,
Pr (E1 (IR ) | j ∈
/ IR )). Now, if we expand Pr (E1 (IR )),






/ IR
/ IR ) Pr E1 (IR ) | j ∈
Pr E1 (IR ) = Pr ( j ∈ IR ) Pr E1 (IR ) | j ∈ IR + Pr ( j ∈




/ IR = p + Pr E1 (IR′ )
≤ Pr ( j ∈ IR ) + Pr E1 (IR ) | j ∈
As Pr (E1 (IR )) ≥ 1/4 and p =

4 ln n
α

≤ 1/8 (since α ≥ 32 ln n), we have,


1/4 ≤ 1/8 + Pr E1 (IR′ )

and therefore, Pr (E1 (IR′ )) ≥ 1/8.
It remains to show that Pr (E2 (IR ) | j ∈ IR ) ≥ Pr (E1 (IR′ )). To see this, note that conditioned on j ∈ IR , the distribution of sampling all constraints other than j is exactly the same as
the distribution of IR′ . Therefore, for any instance IR′ drawn from this distribution, there is a
unique instance IR sampled from the original constraint sampling distribution conditioned on
j ∈ IR . For any such (IR′ , IR ) pair, we have opt (IR ) ≤ opt (IR′ ) + Cost( j) (≤ opt (IR′ ) + Cost(I))
since satisfying the constraint j ∈ IR requires increasing the value of the objective function
opt
in IR′ by at most Cost( j). Therefore if opt (IR′ ) + Cost(I) ≤ 8α (i.e., E1 happens to IR′ ), then
opt
opt (IR ) ≤ 8α (i.e., E2 happens to IR conditioned on j ∈ IR ). Hence,




Pr E2 (IR ) | j ∈ IR ≥ Pr E1 (IR′ ) ≥ 1/8

Plugging in this bound in Equation (4), we obtain that Pr ( j ∈ IR | E2 ) ≥

ln n
2α .

4.2 An α-estimation of Covering ILPs in the Streaming Setting
We now prove Theorem 3. Throughout this section, for simplicity of exposition, we assume
that α ≥ 32 ln n (otherwise the space bound in Theorem 3 is enough to store the whole input
and solve the problem optimally), the value of cmax is provided to the algorithm, and x is a
vector of binary variables, i.e., x ∈ {0, 1}m (hence covering ILP instances are always referring
to covering ILP instances with binary variables); in Section 4.3, we describe how to eliminate
the later two assumptions.
Algorithm overview. For any covering ILP instance I := ILPCover ( A, b, c), our algorithm estimates opt := opt (I) in two parts running in parallel. In the first part, the goal is simply to

16

compute Cost(I) (see Claim 4.3). For the second part, we design a tester algorithm (henceforth, Tester) that given any “guess” k of the value of opt, if k ≥ opt, Tester accepts k w.p. 1
opt
and for any k where Cost(I) ≤ k ≤ 32α , w.h.p. Tester rejects k.
Let K := {2γ }γ∈[⌈log(mcmax )⌉] ; for each k ∈ K (in parallel), we run Tester(k). At the end
of the stream, the algorithm knows Cost(I) (using the output of the part one), and hence it
can identify among all guesses that are at least Cost(I), the smallest guess accepted by Tester
(denoted by k∗ ). On one hand, k∗ ≤ opt since for any guess k ≥ opt, k ≥ Cost(I) also
opt
(since opt ≥ Cost(I)) and Tester accepts k. On the other hand, k∗ ≥ 32α w.h.p. since (i ) if
opt
opt
opt
opt
Cost(I) ≥ 32α , k∗ ≥ Cost(I) ≥ 32α and (ii ) if Cost(I) < 32α , the guess 32α will be rejected
w.h.p. by Tester. Consequently, 32α · k∗ is an O(α)-estimation of opt (I).
We first show that one can compute the Cost of a covering ILP presented in a stream using
a simple dynamic programming algorithm.
Claim 4.3. For any I := ILPCover ( A, b, c) presented by a stream of columns, Cost(I) can be computed
in space O(nbmax log cmax ) bits.
Proof. We maintain arrays Cost j [y] ← +∞ for any j ∈ [n] and y ∈ [bmax ]: Cost j [y] is the
minimum cost for achieving a coverage of y for the j-th constraint. Define Cost j [y] = 0 for
y ≤ 0. Upon arrival of h Ai , ci i, compute Cost j [y] = min(Cost j [y], Cost j [y − a j,i ] + ci ), for every
y from b j down to 1. We then have Cost(I) = max j Cost j [b j ].
To continue, we need the following notation. For any vector v with dimension d and any
set S ⊆ [d], v(S) denotes the projection of v onto the dimensions indexed by S. For any two
vectors u and v, let min(u, v) denote a vector w where at the i-th dimension: wi = min(ui , vi ),
i.e., the coordinate-wise minimum. We now provide the aforementioned Tester algorithm.
Tester(k): An algorithm for testing a guess k of the optimal value of a covering ILP.
Input: An instance I := ILPCover ( A, b, c) presented as a stream h A1 , c1 i, . . ., h Am , cm i, a
parameter α ≥ 32 ln n, and a guess k ∈ K.
opt
Output: ACCEPT if k ≥ opt and REJECT if Cost(I) ≤ k ≤ 32α . The answer could be either
opt
ACCEPT or REJECT if 32α < k < opt.
1. Preprocessing:
c ← 0m ,
(i) Maintain an n-dimensional vector bres ← b, an m-dimensional vector e
e ← 0n × m .
and an n × m dimensional matrix A

(ii) Let V be a subset of [n] obtained by sampling each element in [n] independently
with probability p := 4 ln n/α.
2. Streaming: when a pair h Ai , ci i arrives:
(i) If ci > k, directly continue to the next input pair of the stream. Otherwise:
(ii) Prune step: Let ui := min(bres , Ai ) (the coordinate-wise minimum). If kui k1 ≥
n ·bmax
α , update bres ← bres − u i (we say h A i , c i i is pruned by Tester in this case).
ei ← ui (V ), and e
Otherwise, assign A
ci ← ci .

3. At the end of the stream, solve the following covering ILP (denoted by Itester ):
e ≥ bres (V )
min e
c · x s.t. Ax

If opt (Itester ) is at most k, ACCEPT; otherwise REJECT.

17

ei ←
We first make the following observation. In the prune step of Tester, if we replace A
′
e
ui (V ) by Ai ← Ai (V ), the solution of the resulting covering ILP instance (denoted by Itester
)
′
has the property that opt (Itester ) = opt (Itester ) (we use Itester only to control the space requirement). To see this, let bres i denotes the content of the vector bres when h Ai , ci i arrives.
By construction, (ui ) j := min((bres i ) j , a j,i ), and hence if (ui ) j 6= a j,i , then both (ui ) j and a j,i
are at least (bres i ) j , which is at least (bres ) j (since every dimension of bres is monotonically
decreasing). However, for any integer program ILPCover ( A, b, c), changing any entry a j,i of
A between two values that are at least b j does not change the optimal value, and hence
′
) = opt (Itester ). To simplify the proof, in the following, when concerning opt(Itester ),
opt (Itester
′
.
we redefine Itester to be Itester
We now prove the correctness of Tester in the following two lemmas.


Lemma 4.4. For any guess k ≥ opt, Pr Tester(k) = ACCEPT = 1.
Proof. Fix any optimal solution x∗ of I ; we will show that x∗ is a feasible solution for
c · x∗ ≤ c · x∗ ≤ opt, this will show that
c, we have e
Itester , and since by the construction of e
opt (Itester ) ≤ opt ≤ k and hence Tester(k) = ACCEPT.
Fix a constraint j in Itester as follows:

∑
i∈[m ]

e
a j,i xi ≥ bres (V ) j

If j ∈
/ V, bres (V ) j = 0 and the constraint is trivially satisfied for any solution x∗ . Suppose
j ∈ V and let P denote the set of (indices of) pairs that are pruned. By construction of the
Tester, bres (V ) j = max(b j − ∑ i∈ P a j,i , 0). If bres (V ) j = 0, again the constraint is trivially satisfied.
Suppose bres (V ) j = b j − ∑i∈ P a j,i . The constraint j can be written as

∑ eaj,i xi ≥ bj − ∑ aj,i
i∈ P

i

By construction of the tester, e
a j,i = 0 for all i that are pruned and otherwise e
a j,i = a j,i . Hence,
we can further write the constraint j as

∑ aj,i xi ≥ bj − ∑ aj,i
i∈ P

i/
∈P

Now, since x∗ satisfies the constraint j in I ,

∑
i∈[m ]

a j,i xi∗ ≥ b j

∑ aj,i x∗ ≥ bj − ∑ aj,i xi∗

i/
∈P

i∈ P

≥ b j − ∑ a j,i
i∈ P

(xi∗ ≤ 1)

and the constraint j is satisfied. Therefore, x∗ is a feasible solution of Itester ; this completes
the proof.
opt
We now show that Tester will reject guesses that are smaller than 32α . We will only prove
that the rejection happens with probability 3/4; however, the probability of error can be
reduced to any δ < 1 by running O(log 1/δ) parallel instances of the Tester and for each
guess, REJECT if any one of the instances outputs REJECT and otherwise ACCEPT. In our
case δ = O(|K |−1 ) so we can apply union bound for all different guesses.


opt
Lemma 4.5. For any guess k where Cost(I) ≤ k < 32α , Pr Tester(k) = REJECT ≥ 3/4.
18



Proof. By construction of Tester(k), we need to prove that Pr opt (Itester ) > k ≥ 3/4. Define
the following covering ILP I ′ :

b ≥ bres (V )
min e
c · x s.t. Ax

bi = Ai if h Ai , ci i is not pruned by Tester, and A
bi = 0n otherwise. In Tester(k), for
where A
each pair h Ai , ci i that is not pruned, instead of storing the entire vector Ai , we store the
ei in Itester ). This
projection of Ai onto dimensions indexed by V (which is the definition of A
′
is equivalent to performing constraint sampling on I with a sampling rate of p = 4 ln n/α.
opt(I ′ )
Therefore, by Lemma 4.1, with probability at least 3/4, opt (Itester ) + Cost(I ′ ) ≥ 8α . Since

Cost(I ′ ) ≤ Cost(I) ≤ k <

opt(I )
32α ,

opt (Itester ) ≥

this implies that

opt (I ′ ) opt (I)
opt (I ′ )
− Cost(I ′ ) >
−
.
8α
8α
32α

Therefore, we only need to show that opt (I ′ ) ≥
opt(I )
32α

opt(I )
2

since then opt (Itester ) >

opt(I )
16α

(I )
− opt
32α =

> k and Tester will reject k.
opt(I )
To show that opt (I ′ ) ≥ 2 , we first note that for any optimal solution x∗ of I ′ , if we
further set xi∗ = 1 for any pair h Ai , ci i that are pruned, the resulting xi∗ is a feasible solution
for I . Therefore, if we show that the total weight of the h Ai , ci i pairs that are pruned is at
opt
opt
most 2 , opt (I ′ ) must be at least 2 or we will have a solution for I better than opt (I).
To see that the total weight of the pruned pairs is at most opt/2, since only pairs with
opt
ci ≤ k (≤ 32α ) will be considered, we only need to show that at most 16α pairs can be pruned.
By the construction of the prune step, each pruned pair reduces the ℓ1 -norm of the vector bres
by an additive factor of at least nbαmax . Since bres is initialized to be b and kbk1 ≤ nbmax , at most
α (≤ 16α) pairs can be pruned. This completes the proof.
We now finalize the proof of Theorem 3.
Proof of Theorem 3. We run the algorithm described in the beginning of this section. The
correctness of the algorithm follows from Claim 4.3 and Lemmas 4.4 and 4.5. We now analyze
the space complexity of this algorithm. We need to run the algorithm in Claim 4.3 to come (nbmax ) space. We also need to run Tester for O(log (m · cmax ))
pute Cost(I), which require O
different guesses of k.
In Tester(k), we need O(n log bmax ) bits to store the vector bres and O(m log cmax ) bits to
e requires O(mnbmax /α · (log n/α) · (log amax log n))
maintain the vector e
c. Finally, the matrix A
ei of A
e is either 0n or ui (V ) where kui k <
bits to store. This is because each column A
1
n ·bmax
n ·bmax
n ·bmax
<
.
Since
u
,
there
are
at
most
non-zero
entries
in
u
.
Therefore,
after
k
k
i 1
i
α
α
α
ei ) in expectation the number of non-zero entries in A
ei is at
projecting ui to V (to obtain A
nbmax
2
e
most O(nbmax /α ). Using the Chernoff bound w.h.p at most O( α2 ) non-zero entries of ui
ei , where each entry needs O(log amax log n) bits to store. Note that the space
remain in each A
complexity of the algorithm can be made deterministic by simply terminating the execution
ei has (c · nbmax
when at least one set A
) non-zero entries (for a sufficiently large constant
α2
c > 1); as this event happens with o(1) probability, the error probability of the algorithm
increases only by o(1). Finally, as all entries in ( A, b, c) are poly(n)-bounded, the total space
e ((mn/α2 ) · bmax + m + nbmax ).
requirement of the algorithm is O
We also make the following remark about α-approximating covering ILPs.
Remark 4.6. The simple algorithm described in Section 1.2 for α-approximating set cover can also be
e (mnbmax /α): Group
extended to obtain an α-approximation algorithm for covering ILPs in space O
the columns by the weights and merge every α sets for each group independently.
19

4.3 Further Remarks
We now briefly describe how to eliminate the assumptions that variables are binary and cmax
is given to the algorithm.
Binary variables versus integer variables. We point out that any algorithm that solves covering ILP with binary variables in the streaming setting, can also be used to solve covering ILP
with non-negative integer variables (or shortly, integer variables), while increasing the number
of columns by a factor of O(log bmax ).
To see this, given any covering ILP instance ILPCover ( A, b, c) (with integer variables),
we replace each h Ai , ci i pair with O(log bmax ) pairs (or columns) where the j-th pair (j ∈
[⌈log bmax ⌉]) is defined to be h2j−1 Ai , 2j−1 ci i. Every combination of the corresponding j binary variables maps to a unique binary representation of the variable xi in ILPCover ( A, b, c) for
xi = O(bmax ). Since no variable in ILPCover ( A, b, c) needs to be more than bmax , the correctness
of this reduction follows.
Knowing cmax versus not knowing cmax . As we pointed out earlier, the assumption that the
value of cmax is provided to the algorithm is only for simplicity; here we briefly describe how
to eliminate this assumption. Our algorithm uses cmax to determine the range of opt, which
determines the set of guesses K that Tester needs to run. If cmax is not provided, one natural
fix is to use the same randomness (i.e., the same set V) for all testers, and whenever a larger
ci arrives, create a tester for each new guess by duplicating the state of Tester for the current
largest guess and continue from there (the correctness is provided by the design of our Tester).
However, if we use this approach, since we do not know the total number of guesses
upfront, we cannot boost the probability of success to ensure that w.h.p. no tester fails (if cmax
is poly(n)-bounded, the number of guesses is O(log(ncmax )) = O(log n), O(log log n) parallel
copies suffice, and though we do not know the value of the constant, log n copies always
suffice; but this will not be the case for general cmax ). To address this issue, we point out that
it suffices to ensure that the copy of Tester that runs a specific guess k′ succeed w.h.p., where
opt
k′ is the largest power of 2 with k′ ≤ 32α . To see this, we change the algorithm to pick the
largest rejected guess k∗ and return 64αk∗ (previously, it picks the smallest accepted guess k
opt
and returns 32αk), if k′ is correctly rejected by the tester, k∗ ≥ k′ ≥ 64α . On the other hand, for
any guess no less than opt, Tester accepts it w.p. 1, and hence k∗ ≤ opt. Therefore, as long as
Tester rejects k′ correctly, the output of the algorithm is always an O(α)-estimation and hence
we do not need the knowledge of cmax upfront.
The set multi-cover problem. For the set multi-cover problem, Theorem 3 gives an αe ( mnb2max + m + nbmax ); here, bmax is the maximum demand
estimation algorithm using space O
α
of the elements. However, we remark that if sets are unweighted, a better space requirement
e ( mn2 + m + n) is achievable for this problem: Instead of running the tester for multiple
of O
α
guesses, just run it once with the following changes. In the prune step, change from “kui k1 ≥
nbmax
n
α ” to “k u i k1 ≥ α ”; and output est : = # pruned + 8α ( opt (I tester ) + bmax ), where # pruned is the
number of sets that are pruned. One one hand, est ≥ opt w.h.p since # pruned plus the optimal
solution of the residual covering ILP (denoted by opt res ) is a feasible solution of I , and by
Lemma 4.1, w.h.p. 8α(opt (Itester ) + bmax ) ≥ optres . One the other hand, est = O(α · opt ) since
# pruned ≤ αbmax ≤ α · opt (bmax sets is needed even for covering one element); opt (Itester ) ≤ opt
and bmax ≤ opt, which implies 8α(opt (Itester ) + bmax ) ≤ 8α(opt + opt ) = O(α · opt ).

5 An Ω(mn/α2 )-Space Lower Bound for α-Estimate Set Cover
Our algorithm in Theorem 3 suggests that there exists at least a factor α gap on the space
requirement of α-approximation and α-estimation algorithms for the set cover problem. We
now show that this gap is the best possible. In other words, the space complexity of our
algorithm in Theorem 3 for the original set cover problem is tight (up to logarithmic factors)
20

even for random arrival streams. Formally,
Theorem 4.
qLet S be a collection of m subsets of [n] presented one by one in a random order. For
any α = o( logn n ) and any m = poly(n), any randomized algorithm that makes a single pass over

S and outputs an α-estimation of the set cover problem with probability 0.9 (over the randomness of
e ( mn2 ) bits of space.
both the stream order and the algorithm) must use Ω
α
q
Fix a (sufficiently large) value for n, m = poly(n), and α = o( logn n ); throughout this

section, SetCoverest refers to the problem of α-estimating the set cover problem with m + 1
sets (see footnote 4) defined over the universe [n] in the one-way communication model,
whereby the sets are partitioned between Alice and Bob.

Overview. We start by introducing a hard distribution Dest for SetCoverest in the spirit of the
distribution Dapx in Section 3. However, since in SetCoverest the goal is only to estimate the
size of the optimal cover, “hiding” one single element (as was done in Dapx ) is not enough for
the lower bound. Here, instead of trying to hide a single element, we give Bob a “block” of
elements and his goal would be to decide whether this block appeared in a single set of Alice
as a whole or was it partitioned across many different sets6. Similar to Dapx , distribution
Dest is also not a product distribution; however, we introduce a way of decomposing Dest
into a convex combination of product distributions and then exploit the simplicity of product
distributions to prove the lower bound.
Nevertheless, the distribution Dest is still “adversarial” and hence is not suitable for proving the lower bound for random arrival streams. Therefore, we define an extension to the
original hard distribution as Dext which randomly partitions the sets of distribution Dest between Alice and Bob. We prove a lower bound for this distribution using a reduction from
protocols over Dest . Finally, we show how an algorithm for set cover over random arrival
streams would be able to solve instances of SetCoverest over Dext and establish Theorem 4.

5.1 A Hard Input Distribution for SetCoverest
Consider the following distribution Dest for SetCoverest .
Distribution Dest . A hard input distribution for SetCoverest .
Notation. Let F be the collection of all subsets of [n] with cardinality

n
10α .

• Alice. The input of Alice is a collection of m sets S = (S1 , . . . , Sm ), where for any
i ∈ [m], Si is a set chosen independently and uniformly at random from F .
• Bob. Pick θ ∈ {0, 1} and i∗ ∈ [m] independently and uniformly at random; the input
of Bob is a single set T defined as follows.
− If θ = 0, then T is a set of size α log m chosen uniformly at random from Si∗ .a

− If θ = 1, then T is a set of size α log m chosen uniformly at random from [n] \ Si∗ .

a

Since α = o (

p

n/ log n) and m = poly(n ), the size of T is strictly smaller than the size of Si∗ .

Recall that opt (S , T ) denotes the set cover size of the input instance (S , T ). We first establish
the following lemma regarding the parameter θ and opt (S , T ) in the distribution Dest .
Lemma 5.1. For (S , T ) ∼ Dest :
6 The

actual set given to Bob is the complement of this block; hence the optimal set cover size varies significantly
between the two cases.

21

(i) Pr (opt (S , T ) = 2 | θ = 0) = 1.
(ii) Pr (opt (S , T ) > 2α | θ = 1) = 1 − o(1).
Proof. Part (i) is immediate since by construction, when θ = 0, T ∪ Si∗ = [n]. We now prove
part (ii).
Since a valid set cover must cover T, it suffices for us to show that w.h.p. no 2α sets from
S can cover T. By construction, neither T nor Si∗ contains any element in T, hence T must be
covered by at most 2α sets in S \ {Si∗ }.
Fix a collection Sb of 2α sets in S \ {Si∗ }; we first analyze the probability that Sb covers T
and then take union bound over all choices of 2α sets from S \ {Si∗ }. Note that according
to the distribution Dest , the sets in Sb are drawn independent of T. Fix any choice of T; for
j
each element k ∈ T, and for each set S j ∈ Sb, define an indicator random variable Xk ∈ {0, 1},
j

j

where Xk = 1 iff k ∈ S j . Let X := ∑ j ∑k Xk and notice that:
E[ X ] =

1

j

∑ ∑ E[Xk ] = (2α) · (α log m) · ( 10α ) = α log m/5
j

k

We have,


Pr Sb covers T ≤ Pr ( X ≥ α log m) = Pr ( X ≥ 5 E[ X ]) ≤ exp (−3α log m)
j

where the last equality uses the fact that Xk variables are negatively correlated (which can be
proven analogous to Lemma 3.2) and applies the extended Chernoff bound (see Section 2).
Finally, by union bound,

 m
b
Pr(opt (S , T ) ≤ 2α) ≤ Pr ∃ S covers T ≤
· exp (−3α log m)
2α
≤ exp (2α · log m − 3α log m) = o(1)
Notice that distribution Dest is not a product distribution due to the correlation between
the input given to Alice and Bob. However, we can express the distribution as a convex
combination of a relatively small set of product distributions; this significantly simplifies the
proof of the lower bound. To do so, we need the following definition. For integers k, t and
n, a collection P of t subsets of [n] is called a random (k, t)-partition iff the t sets in P are
constructed as follows: Pick k elements from [n], denoted by S, uniformly at random, and
partition S randomly into t sets of equal size. We refer to each set in P as a block.
An alternative definition of the distribution Dest .
Parameters:

k=

n
5α

p = α log m

t = k/p

1. For any i ∈ [m], let Pi be a random (k, t)-partition in [n] (chosen independently).
2. The input to Alice is S = (S1 , . . . , Sm ), where each Si is created by picking t/2 blocks
from Pi uniformly at random.
3. The input to Bob is a set T where T is created by first picking an i∗ ∈ [m] uniformly
at random, and then picking a block from Pi∗ uniformly at random.
To see that the two formulations of the distribution Dest are indeed equivalent, notice
that (i ) the input given to Alice in the new formulation is a collection of sets of size n/10α
22

chosen independently and uniformly at random (by the independence of Pi ’s), and (ii ) the
complement of the set given to Bob is a set of size α log m which, for i ∗ ∈ R [m], with probability
half, is chosen uniformly at random from Si∗ , and with probability half, is chosen from [n] \ Si∗
(by the randomness in the choice of each block in Pi∗ ).
Fix any δ-error protocol ΠSC (δ < 1/2) for SetCoverest on the distribution Dest . Recall
that ΠSC denotes the random variable for the concatenation of the message of Alice with the
public randomness used in the protocol ΠSC . We further use P := (P1 , . . . , Pt ) to denote the
random partitions ( P1 , . . . , Pt ), I for the choice of the special index i∗ , and θ for the parameter
θ ∈ {0, 1}, whereby θ = 0 iff T ⊆ Si∗ .
We make the following simple observations about the distribution Dest . The proofs are
straightforward.
Remark 5.2. In the distribution Dest ,
1. The random variables S , P , and ΠSC (S) are all independent of the random variable I.
2. For any i ∈ [m], conditioned on Pi = P, and I = i, the random variables Si and T are
independent of each other. Moreover, supp(Si ) and supp(T) contain, respectively, ( tt ) and t
2

elements and both Si and T are uniform over their support.
3. For any i ∈ [m], the random variable Si is independent of both S −i and P −i .

5.2 The Lower Bound for the Distribution Dest
Our goal in this section is to lower bound ICostDest (ΠSC ) and ultimately kΠSC k. We start by
simplifying the expression for ICostDest (ΠSC ).
Lemma 5.3. ICostDest (ΠSC ) ≥ ∑m
i=1 I ( ΠSC ; Si | Pi )
Proof. We have,
ICostDest (ΠSC ) = I (ΠSC ; S) ≥ I (ΠSC ; S | P )
where the inequality holds since (i ) H (ΠSC ) ≥ H (ΠSC | P ) and (ii ) H (ΠSC | S) = H (ΠSC |
S , P ) as ΠSC is independent of P conditioned on S . We now bound the conditional mutual
information term in the above equation.
m

I (ΠSC ; S | P ) =

∑ I (Si; ΠSC | P , S <i )

i=1

(the chain rule for the mutual information, Claim 2.1-(5))
m

=

∑ H (Si | P , S <i ) − H (Si | ΠSC , P , S <i )

i=1
m

≥
=

∑ H (Si | Pi ) − H (Si | ΠSC , Pi )

i=1
m

∑ I (Si; ΠSC | Pi )

i=1

The inequality holds since:
(i) H (Si | Pi ) = H (Si | Pi , P −i , S <i ) = H (Si | P , S <i ) because conditioned on Pi , Si is
independent of P −i and S <i (Remark 5.2-(3)), hence the equality holds by Claim 2.1-(3).
(ii) H (Si | ΠSC , Pi ) ≥ H (Si | ΠSC , Pi , P −i , S <i ) = H (Si | ΠSC , P , S <i ) since conditioning
reduces the entropy, i.e., Claim 2.1-(3).
23

Equipped with Lemma 5.3, we only need to bound ∑i∈[m] I (ΠSC ; Si | Pi ). Note that,
m

∑
i=1

I (ΠSC ; Si | Pi ) =

m

m

i=1

i=1

∑ H (Si | Pi ) − ∑ H (Si | ΠSC , Pi )

(5)

Furthermore, for each i ∈ [m], |supp(Si | Pi )| = ( tt ) and Si is uniform over its support (Re2
mark 5.2-(2)); hence, by Claim 2.1-(1),
m

∑ H (Si | Pi ) =

i=1

m

∑ log
i=1

 
t
t
2



= m · log 2t−Θ(log t) = m · t − Θ(m log t)

(6)

Consequently, we only need to bound ∑m
i=1 H ( Si | ΠSC , Pi ). In order to do so, we show
that ΠSC can be used to estimate the value of the parameter θ, and hence we only need to
establish a lower bound for the problem of estimating θ.
Lemma 5.4. Any δ-error protocol ΠSC over the distribution Dest can be used to determine the value
of θ with error probability δ + o(1).
Proof. Alice sends the message ΠSC (S) as before. Using this message, Bob can compute an
α-estimation of the set cover problem using ΠSC (S) and his input. If the estimation is less
than 2α, we output θ = 0 and otherwise we output θ = 1. The bound on the error probability
follows from Lemma 5.1.
Before continuing, we make the following remark which would be useful in the next
section.
Remark 5.5. We assume that in SetCoverest over the distribution Dest , Bob is additionally provided
with the special index i ∗ .
Note that this assumption can only make our lower bound stronger since Bob can always
ignore this information and solves the original SetCoverest .
Let β be the function that estimates θ used in Lemma 5.4; the input to β is the message
given from Alice, the public coins used by the players, the set T, and (by Remark 5.5) the
special index i ∗ . We have,
Pr( β(ΠSC , T, I ) 6= θ) ≤ δ + o(1)
Hence, by Fano’s inequality (Claim 2.2),
H2 (δ + o(1)) ≥ H (θ | ΠSC , T, I )
h
i
= E H (θ | ΠSC , T, I = i)
i∼ I

=

1
m

m

∑ H (θ | ΠSC , T, I = i)

(7)

i=1

We now show that each term above is lower bounded by H (Si | ΠSC , Pi )/t and hence we
obtain the desired upper bound on H (Si | ΠSC , Pi ) in Equation (5).
Lemma 5.6. For any i ∈ [m], H (θ | ΠSC , T, I = i ) ≥ H (Si | ΠSC , Pi )/t.

24

Proof. We have,
H (θ | ΠSC , T, I = i ) ≥ H (θ | ΠSC , T, Pi , I = i )
(conditioning on random variables reduces entropy, Claim 2.1-(3))
h
i
H (θ | ΠSC , T, Pi = P, I = i )
=
E
P ∼ Pi | I = i

For brevity, let E denote the event (Pi = P, I = i ). We can write the above equation as,
h
i
H (θ | ΠSC , T, Pi , I = i ) =
E
E
H (θ | ΠSC , T = T, E)
P ∼ Pi | I = i T ∼T| E

Note that by Remark 5.2-(2), conditioned on the event E, T is chosen to be one of the blocks
of P = ( B1 , . . . , Bt ) uniformly at random. Hence,
H (θ | ΠSC , T, Pi , I = i ) =

E

P ∼ Pi | I = i

h

t

∑
j=1

H (θ | ΠSC , T = Bj , E) i
t

Define a random variable X := ( X1 , . . . , Xt ), where each X j ∈ {0, 1} and X j = 1 iff
Si contains the block Bj . Note that conditioned on E, X uniquely determines the set Si .
Moreover, notice that conditioned on T = Bj and E, θ = 0 iff X j = 1. Hence,
H (θ | ΠSC , T, Pi , I = i ) =

E

P ∼ Pi | I = i

h

t

∑
j=1

H ( X j | ΠSC , T = Bj , E) i
t

Now notice that X j is independent of the event T = Bj since Si is chosen independent of T
conditioned on E (Remark 5.2-(2)). Similarly, since ΠSC is only a function of S and S is independent of T conditioned on E, ΠSC is also independent of the event T = Bj . Consequently,
by Claim 2.1-(6), we can “drop” the conditioning on T = Bj ,
h

H ( X j | ΠSC , E) i
∑
t
P ∼ Pi | I = i j=1
h H ( X | Π , E) i
SC
≥
E
t
P ∼ Pi | I = i
(sub-additivity of the entropy, Claim 2.1-(4))
h H (S | Π , E) i
SC
i
=
E
t
P ∼ Pi | I = i
(Si and X uniquely define each other conditioned on E)
h H (S | Π , P = P, I = i ) i
SC i
i
=
E
t
P ∼ Pi | I = i
(E is defined as (Pi = P, I = i ))

H (θ | ΠSC , T, Pi , I = i ) =

=

E

t

H (Si | ΠSC , Pi , I = i )
t

Finally, by Remark 5.2-(1), Si , ΠSC , and Pi are all independent of the event I = i, and hence
by Claim 2.1-(6), H (Si | ΠSC , Pi , I = i ) = H (Si | ΠSC , Pi ), which concludes the proof.
By plugging in the bound from Lemma 5.6 in Equation (7) we have,
m

∑ H (Si | ΠSC , Pi ) ≤ H2 (δ + o(1)) · (mt)

i=1

25

Finally, by plugging in this bound together with the bound from Equation (6) in Equation (5),
we get,
m

∑ I (ΠSC ; Si | Pi ) ≥ mt − Θ(m log t) − H2 (δ + o(1)) · (mt)

i=1



= 1 − H2 (δ + o(1)) · (mt) − Θ(m log t)

e (n/α2 ) and δ < 1/2, hence H2 (δ + o(1)) = 1 − ǫ for some constant
Recall that t = k/p = Ω
ǫ bounded away from 0. By Lemma 5.3,


e (mn/α2 )
ICδDest (SetCoverest ) = min ICostDest (ΠSC ) = Ω
ΠSC

To conclude, since the information complexity is a lower bound on the communication complexity (Proposition 2.5), we obtain the following theorem.
p
Theorem 5. For any constant δ < 1/2, any α = o( n/ log n), and any m = poly(n),
e (mn/α2 )
CCδDest (SetCoverest ) = Ω

As a corollary of this result, we have that the space complexity of single-pass streaming
e (mn/α2 ).
algorithms for the set cover problem on adversarial streams is Ω

5.3 Extension to Random Arrival Streams

We now show that the lower bound established in Theorem 5 can be further strengthened
to prove a lower bound on the space complexity of single-pass streaming algorithms in the
random arrival model. To do so, we first define an extension of the distribution Dest , denoted
by Dext , prove a lower bound for Dext , and then show that how to use this lower bound on
the one-way communication complexity to establish a lower bound for the random arrival
model.
We define the distribution Dext as follows.
Distribution Dext . An extension of the hard distribution Dest for SetCoverest .
1. Sample the sets S = {S1 , . . . , Sm , T } in the same way as in the distribution Dest .
2. Assign each set in S to Alice with probability 1/2, and the remaining sets are assigned
to Bob.
We prove that the distribution Dext is still a hard distribution for SetCoverest .
p
Lemma 5.7. For any constant δ < 1/8, α = o( n/ log n), and m = poly(n),
e (mn/α2 )
CCδDext (SetCoverest ) = Ω

Proof. We prove this lemma using a reduction from SetCoverest over the distribution Dest .
Let ΠExt be a δ-error protocol over the distribution Dext . Let δ′ = 3/8 + δ; in the following,
we create a δ′ -error protocol ΠSC for the distribution Dest (using ΠExt as a subroutine).
Consider an instance of the problem from the distribution Dest . Define a mapping σ :
[m + 1] 7→ S such that for i ≤ m, σ(i) = Si and σ(m + 1) = T. Alice and Bob use public
randomness to partition the set of integers [m + 1] between each other, assigning each number
26

in [m + 1] to Alice (resp. to Bob) with probability 1/2. Note that by Remark 5.5, we may
assume that Bob knows the special index i ∗ .
Consider the random partitioning of [m + 1] done by the players. If i ∗ = σ−1 (Si∗ ) is
assigned to Bob, or m + 1 = σ−1 ( T ) is assigned to Alice, Bob always outputs 2. Otherwise,
Bob samples one set from F for each j assigned to him independently and uniformly at
random and treat these sets plus the set T as his “new input”. Moreover, Alice discards the
sets S j = σ( j), where j is assigned to Bob and similarly treat the remaining set as her new
input. The players now run the protocol ΠExt over this distribution and Bob outputs the
estimate returned by ΠExt as his estimate of the set cover size.
Let R denote the randomness of the reduction (excluding the inner randomness of ΠExt ).
Define E as the event that in the described reduction, i ∗ is assigned to Alice and m + 1 is
assigned to Bob. Let Dnew be the distribution of the instances over the new inputs of Alice and
Bob (i.e., the input in which Alice drops the sets assigned to Bob, and Bob randomly generates
the sets assigned to Alice) when E happens. Similarly, we define Eb to be the event that in the
distribution Dext , Si∗ is assigned to Alice and T is assigned to Bob. It is straightforward to
verify that Dnew = (Dext | Eb). We now have,
Pr

Dest ,R



 


 

1
ΠSC errs = · Pr E + Pr E · Pr ΠExt errs
R
2 R
Dnew

(since Bob outputs 2 when E , he will succeed with probability 1/2)
 


 
1
= · Pr E + Pr E · Pr ΠExt errs | Eb
(Dnew = (Dext | Eb))
R
2 R
Dext






Pr
Π
errs
Dext
Ext
1
 
≤ · Pr E + Pr E ·
R
2 R
PrDext Eb
 


1
(PrR (E ) = PrDext (Eb))
= · Pr E + Pr ΠExt errs
2 R
Dext
3
≤ +δ
(PrR (E ) = 3/4)
8
Finally, since δ < 1/8, we obtain a (1/2 − ǫ)-error protocol (for some constant ǫ bounded
away from 0) for the distribution Dest . The lower bound now follows from Theorem 5.
We can now prove the lower bound for the random arrival model.
Proof of Theorem 4. Suppose A is a randomized single-pass streaming algorithm satisfying
the conditions in the theorem statement. We use A to create a δ-error protocol SetCoverest
over the distribution Dext with parameter δ = 0.1 < 1/8.
Consider any input S in the distribution Dext and denote the sets given to Alice by S A
and the sets given to Bob by SB . Alice creates a stream created by a random permutation
of S A denoted by s A , and Bob does the same for SB and obtains sB . The players can now
compute A (hs A , sB i) to estimate the set cover size and the communication complexity of this
protocol equals the space complexity of A. Moreover, partitioning made in the distribution
Dext together with the choice of random permutations made by the players, ensures that
hs A , sB i is a random permutation of the original set S . Hence, the probability that A fails
to output an α-estimate of the set cover problem is at most δ = 0.1. The lower bound now
follows from Lemma 5.7.

27

6 An Ω(mn/α)-Space Lower Bound for Deterministic α-Estimation
In Section 4, we provided a randomized algorithm for α-estimating the set cover problem,
with an (essentially) optimal space bound (as we proved in Section 5); here, we establish
that randomization is crucial for achieving better space bound for α-estimation: any deterministic α-estimation algorithm for the set cover problem requires Ω( mn
α ) bits of space. In
other words, α-approximation and α-estimation are as hard as each other for deterministic
algorithms. Formally,
q
Theorem 6. For any α = o( logn n ) and m = poly(n), any deterministic α-estimation single-pass
streaming algorithm for the set cover problem requires Ω(mn/α) bits of space.

Before continuing, we make the following remark. The previous best lower bound for deterministic algorithm asserts that any O(1)-estimation algorithm requires Ω(mn) bits of space
even allowing constant number of passes [10]. This lower bound can be stated more generally in
terms of its dependence on α: for any α ≤ log n − O(log log n), any deterministic α-estimation
algorithm requires space of Ω(mn/α · 2α ) bits (see Lemma 11 and Theorem 3 in [10]). Our
bound in Theorem 6 provide an exponential improvement over this bound for single-pass
algorithms.
Recall the definition of SetCoverest from Section 5 for a fixed choice of parameters n, m, and
α. We define the following hard input distribution for deterministic protocols of SetCoverest .
Distribution Ddet . A hard input distribution for deterministic protocols of SetCoverest .
Notation. Let F be the collection of all subsets of [n] with cardinality n/10α.

• Alice. The input to Alice is an m-subset S ⊆ F chosen uniformly at random.
• Bob. Toss a coin θ ∈ R {0, 1}; let the input to Bob be the set T, where if θ = 0, T ∈ R S
and otherwise, T ∈ R F \ S .
We stress that distribution Ddet can only be hard for deterministic protocols; Alice can
simply run a randomized protocol for checking the equality of each Si with T (independently
for each Si ∈ S ) and since the one-way communication complexity of the Equality problem
with public randomness is O(1) (see, e.g., [21]), the total communication complexity of this
protocol is O(m). However, such approach is not possible for deterministic protocols since
deterministic communication complexity of the Equality problem is linear in the input size
(again, see [21]).
q
The following lemma can be proven similar to Lemma 5.1 (assuming that α = o( logn n )).
Lemma 6.1. For (S , T ) ∼ Ddet :

(i) Pr (opt (S , T ) = 2 | θ = 0) = 1.
(ii) Pr (opt (S , T ) > 2α | θ = 1) = 1 − 2−Ω(n/α) .
To prove Theorem 6, we use a reduction from the Sparse Indexing problem of [26]. In
SparseIndexing kN , Alice is given a set S of k elements from a universe [ N ] and Bob is given an
element e ∈ [ N ]; Bob needs to output whether or not e ∈ S. The crucial property of this
problem that we need in our proof is that the communication complexity of Sparse Indexing
depends on the success probability required from the protocol.
The following lemma is a restatement of Theorem 3.2 from [26].
Lemma 6.2 ([26]). Consider the following distribution DSI for SparseIndexing kN :
28

• Alice is given a k-subset S ⊆ [ N ] chosen uniformly at random.
• With probability half Bob is given an element e ∈ S uniformly at random, and with probability
half Bob receives a random element e ∈ [ N ] \ S.
For any δ < 1/3, the communication complexity of any deterministic δ-error protocol over distribution
DSI is Ω(min {k log(1/δ), k log( N/k)}) bits.
We now show that how a deterministic protocol for SetCoverest can be used to solve the
hard distribution of SparseIndexing kN described in the previous lemma.
Notice that there is a simple one-to-one mapping φ from an instance (S, e) of SparseIndexing kN
to an instance (S , T ) of SetCoverest with parameters n and m where N = ( nn ) and k = m. Fix
10α
any arbitrary bijection σ : [ N ] 7→ F ; we map S to the collection S = {σ( j) | j ∈ S} and map e
to the set T = [n] \ σ(e). Under this transformation, if we choose (S, e) ∼ DSI the SetCoverest
distribution induced by φ(S, e) is equivalent to the distribution Ddet . Moreover, the answer of
(S, e) for the SparseIndexingkN problem is YES iff θ = 0 in (S , T ). We now proceed to the proof
of Theorem 6.
Proof of Theorem 6. Let ΠSC be a deterministic protocol for the SetCoverest problem; we
use ΠSC to design a δ-error protocol ΠSI for SparseIndexing kN on the distribution DSI for δ =
2−Ω(n/α) . The lower bound on message size of ΠSC then follows from Lemma 6.2.
Protocol ΠSI works as follows. Consider the mapping φ from (S, e) to (S , T ) defined
before. Given an instance (S, e) ∼ DSI , Alice and Bob can each compute their input in φ(S, e)
without any communication. Next, they run the protocol ΠSC (S , T ) and if the set cover size
is less than 2α Bob outputs YES and otherwise outputs NO.
We argue that ΠSI is a δ-error protocol for SparseIndexing kN on the distribution DSI . To see
this, recall that if (S, e) ∼ DSI then (S , T ) ∼ Ddet . Let E be an event in the distribution Ddet ,
where θ = 1 but opt < 2α. Note that since ΠSC is a deterministic α-approximation protocol
and never errs, the answer for ΠSI would be wrong only if E happens. We have,


 
ΠSI (S, e) errs ≤
Pr
E = 2−Ω(n/α)
Pr
( S,e )∼DSI

(S ,T )∼Ddet

where the equality is by Lemma 6.1. This implies that ΠSI is a δ-error protocol for the distribution DSI . By Lemma 6.2,

kΠSC k = kΠSI k = Ω(min(k · log 1/δ, k log( N/k))) = Ω(mn/α)
As one-way communication complexity is a lower bound on the space complexity of singlepass streaming algorithm we obtain the final result.

Acknowledgements
We thank Piotr Indyk for introducing us to the problem of determining single-pass streaming
complexity of set cover, and the organizers of the DIMACS Workshop on Big Data through
the Lens of Sublinear Algorithms (August 2015) where this conversation happened. We are
also thankful to anonymous reviewers for many valuable comments.

29

References
[1] Alon, N., Matias, Y., and Szegedy, M. The space complexity of approximating the
frequency moments. In STOC (1996), ACM, pp. 20–29.
[2] Bar-Yossef, Z., Jayram, T. S., Kumar, R., and Sivakumar, D. An information statistics
approach to data stream and communication complexity. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada,
Proceedings (2002), pp. 209–218.
[3] Bar-Yossef, Z., Jayram, T. S., Kumar, R., and Sivakumar, D. Information theory methods in communication complexity. In Proceedings of the 17th Annual IEEE Conference on
Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002 (2002), pp. 93–102.
[4] Barak, B., Braverman, M., Chen, X., and Rao, A. How to compress interactive communication. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010,
Cambridge, Massachusetts, USA, 5-8 June 2010 (2010), pp. 67–76.
[5] Chakrabarti, A., Cormode, G., and McGregor, A. Robust lower bounds for communication and stream computation. In Proceedings of the 40th Annual ACM Symposium on
Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008 (2008), pp. 641–
650.
[6] Chakrabarti, A., Shi, Y., Wirth, A., and Yao, A. C. Informational complexity and the
direct sum problem for simultaneous message complexity. In 42nd Annual Symposium on
Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA
(2001), pp. 270–278.
[7] Chakrabarti, A., and Wirth, T. Incidence geometries and the pass complexity of semistreaming set cover. CoRR, abs/1507.04645. To appear in Symposium on Discrete Algorithms
(SODA) (2016).
[8] Cormode, G., Karloff, H. J., and Wirth, A. Set cover algorithms for very large datasets.
In Proceedings of the 19th ACM Conference on Information and Knowledge Management, CIKM
2010, Toronto, Ontario, Canada, October 26-30, 2010 (2010), pp. 479–488.
[9] Cover, T. M., and Thomas, J. A. Elements of information theory (2. ed.). Wiley, 2006.
[10] Demaine, E. D., Indyk, P., Mahabadi, S., and Vakilian, A. On streaming and communication complexity of the set cover problem. In Distributed Computing - 28th International
Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings (2014), pp. 484–
498.
[11] Dinur, I., and Steurer, D. Analytical approach to parallel repetition. In Symposium
on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014 (2014),
pp. 624–633.
[12] Emek, Y., and Rosén, A. Semi-streaming set cover - (extended abstract). In Automata,
Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I (2014), pp. 453–464.
[13] Feige, U. A threshold of ln n for approximating set cover. J. ACM 45, 4 (1998), 634–652.
[14] Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., and Zhang, J. On graph problems
in a semi-streaming model. Theor. Comput. Sci. 348, 2-3 (2005), 207–216.

30

[15] Har-Peled, S., Indyk, P., Mahabadi, S., and Vakilian, A. Towards tight bounds for the
streaming set cover problem. To appear in PODS (2016).
[16] Impagliazzo, R., and Kabanets, V. Constructive proofs of concentration bounds. In
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,
13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM
2010, Barcelona, Spain, September 1-3, 2010. Proceedings (2010), pp. 617–631.
[17] Indyk, P., Mahabadi, S., and Vakilian, A. Towards tight bounds for the streaming set
cover problem. CoRR abs/1509.00118 (2015).
[18] Jayram, T. S., and Woodruff, D. P. Optimal bounds for johnson-lindenstrauss transforms and streaming problems with sub-constant error. In Proceedings of the TwentySecond Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco,
California, USA, January 23-25, 2011 (2011), pp. 1–10.
[19] Johnson, D. S. Approximation algorithms for combinatorial problems. J. Comput. Syst.
Sci. 9, 3 (1974), 256–278.
[20] Kapralov, M., Khanna, S., and Sudan, M. Approximating matching size from random streams. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014 (2014), pp. 734–751.
[21] Kushilevitz, E., and Nisan, N. Communication complexity. Cambridge University Press,
1997.
[22] Lund, C., and Yannakakis, M. On the hardness of approximating minimization problems. J. ACM 41, 5 (1994), 960–981.
[23] Muthukrishnan, S. Data streams: Algorithms and applications. Foundations and Trends
in Theoretical Computer Science 1, 2 (2005).
[24] Nisan, N. The communication complexity of approximate set packing and covering. In
Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga,
Spain, July 8-13, 2002, Proceedings (2002), pp. 868–875.
[25] Panconesi, A., and Srinivasan, A. Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds. SIAM J. Comput. 26, 2 (1997), 350–368.
[26] Saglam, M. Tight bounds for data stream algorithms and communication problems. PhD thesis,
Simon Fraser University, 2011.
[27] Saha, B., and Getoor, L. On maximum coverage in the streaming model & application
to multi-topic blog-watch. In Proceedings of the SIAM International Conference on Data
Mining, SDM 2009, April 30 - May 2, 2009, Sparks, Nevada, USA (2009), pp. 697–708.
[28] Slavík, P. A tight analysis of the greedy algorithm for set cover. J. Algorithms 25, 2 (1997),
237–254.

31

A

A Lower Bound for ICδDIndex (Indexnk )

In this section we prove Lemma 3.4. As stated earlier, this lemma is well-known and is proved
here only for the sake of completeness.
Proof of Lemma 3.4. Consider the following “modification” to the distribution DIndex . Suppose we first sample a 2k-set P ⊆ [n], and then let the input to Alice be a k-set A ⊂ P chosen
uniformly at random, and the input to Bob be an element a ∈ P chosen uniformly at random.
It is an easy exercise to verify that this modification does not change the distribution DIndex .
However, this allows us to analyze the information cost of any protocol ΠIndex over DIndex
easier. In particular,
ICostDIndex (ΠIndex ) = I ( A; ΠIndex )

≥ I ( A; ΠIndex | P )
= H ( A | P ) − H ( A | ΠIndex , P )
= 2k − Θ(log k) − H ( A | ΠIndex , P )

where the inequality holds since (i ) H (ΠIndex ) ≥ H (ΠIndex | P ) and (ii ) H (ΠIndex | A) =
H (ΠIndex | A, P ) as ΠIndex is independent of P conditioned on A.
We now bound H ( A | ΠIndex , P ). Define θ ∈ {0, 1} where θ = 1 iff a ∈ A. Note that a
δ′ -error protocol for Index is also a δ′ -error (randomized) estimator for θ (given the message
ΠIndex , the public randomness used along with the message, and the element a). Hence, using
Fano’s inequality (Claim 2.2),
H2 (δ′ ) ≥ H (θ | ΠIndex , a)

≥ H (θ | ΠIndex , a, P )
(conditioning decreases entropy, Claim 2.1-(3))
h
i
H (θ | ΠIndex , a = a, P = P)
= E
E
P ∼ P a∼ a |P= P

Conditioned on P = P, a is chosen uniformly at random from P. Define X := ( X1 , . . . , X2k ),
where Xi = 1 if i-th element in P belongs to A and Xi = 0 otherwise. Using this notation, we
have θ = Xi conditioned on P = P, and a = a being the i-th element of P. Hence,
i
1
·
H
(
X
|
Π
,
a
=
a,
P
=
P
)
i
Index
∑ 2k
P∼P
i=1
h 2k 1
i
= E ∑
· H ( Xi | ΠIndex , P = P)
P∼P
2k
i=1
(Xi and ΠIndex are independent of a = a conditioned on P = P, and Claim 2.1-(6))
h
i
1
≥
· E H ( A | ΠIndex , P = P)
(sub-additivity of the entropy, Claim 2.1-(4))
2k P∼P
1
= H ( A | ΠIndex , P )
2k

H2 (δ′ ) ≥ E

h

2k

Consequently,
H ( A | ΠIndex , P ) ≤ 2k · H2 (δ′ )
Finally, since δ′ < 1/2 and hence H2 (δ′ ) = (1 − ǫ) for some ǫ bounded away from 0, we have,
ICostDIndex (ΠIndex ) ≥ 2k · (1 − H2 (δ′ )) − Θ(log k) = Ω(k)

32

