CS 6815: Pseudorandomness and Combinatorial Constructions Fall 2022

Lecture 3: Aug 30, 2022

Lecturer: Eshan Chattopadhyay Scribe: Noam Ringach

1 Introduction
We begin by recalling our definition of BPP:

Definition 1.1 (BPP). A language L is in BPPif there exists a polynomial time probabilistic Turing
Machine (PTM) A such that for all possible inputs x we have that
2
Pr [A(x, r) = L(x)] ≥ .
r∼{0,1}poly(|x|) 3

In the last lecture, we saw that to increase the accuracy of our algorithm from at least 23 to at
least 1 − ε (i.e., decreasing our errors from at most 31 to at most ε), we can come up with a new
PTM B defined as

Algorithm 1 Definition of B based on A.

Require: Original PTM A, error rate ε > 0
t ← log 1ε
for i ∈ [t] do
Sample ri ∼ {0, 1}poly(|x|)
Yi ← A(x, ri )
end for
return Maj(Y1 , . . . , Yt )

Furthermore, B has the following guarantees on accuracy, runtime, and randomness, where
T (n) = poly(n) is the runtime of A, R(n) = poly(|x|) is the randomness usage of A, and c is an
overhead constant from B.

Algorithm Accuracy Runtime Randomness

B 1−ε c · T (n) · log 1ε c · R(n) log 1ε

Table 1: Accuracy, runtime, and randomness usage of B.

In this lecture, we explore the following question.

Question 1. Can we construct another algorithm that uses less randomness than B to achieve the
same 1 − ε error rate?

2 Pairwise Independence
In the process of constructing such an algorithm, we will need to introduce a variation on the
independence of random variables (RVs) called pairwise independence.

1
Lecture 3: Aug 30, 2022 2

Definition 2.1 (Pairwise Independence). A collection of RVs X1 , X2 , . . . , XN on the domain X is

said to be pairwise independent if the following two conditions are satisfied:

1. For all i, j ∈ [N ] such that i ̸= j, we have that Xi and Xj are independent.

2. Each Xi is uniform on X .

We can easily construct a straightforward example of three pairwise independent RVs using the
XOR function.

Example 2.2. Say that we uniformly sample x1 , x2 ∼ {0, 1} = F2 and define x3 = x1 ⊕ x2 . Then
{x1 , x2 , x3 } is a collection of pairwise independent RVs.

Proof. To see that x1 , x2 , x3 are pairwise independent, all we need to show is that {x1 , x3 } and
{x2 , x3 } are independent, since {x1 , x2 } are independent by assumption. We will show that {x2 , x3 }
are independent, and the logic for {x1 , x3 } being independent will be identical.
Take any a, b ∈ F2 . Then

Pr [x3 = a ∧ x2 = b] = Pr[x3 = a | x2 = b] Pr[x2 = b].

x2 ,x3 x3 x2

Of course, Prx2 [x2 = b] = 21 by definition. Additionally, we see that Prx3 [x3 = a | x2 = b] = 12

because for any fixed x2 = b, there is exactly one value of x1 so that x1 ⊕ x2 = a and one value so
that x1 ⊕ x2 ̸= a. Putting this together, we get that

Pr [x3 = a ∧ x2 = b] = Pr[x3 = a | x2 = b] Pr[x2 = b]

x2 ,x3 x3 x2
1 1
= ·
2 2
= Pr[x3 = a] Pr[x2 = b],
x3 x2

meaning that x3 and x2 are indeed independent.

We can generalize this example to create even more pairwise independent RVs.

Example 2.3. For any uniformly sampled x1 , . . . , xr ∼ F2 , take any non-empty subset S ⊆ [r] and
define
M
ZS = xi .
i∈S

Then the collection Z = {ZS }S⊆[r] is a collection of 2r − 1 pairwise independent RVs.

Proof. First, we easily see that |Z| = 2r − 1 because there are 2r possible subsets of [r] and we are
excluding the empty subset, so we have 2r − 1 non-empty subsets over which we are indexing (i.e.,
there are only 2r − 1 non-trivial ways we can take XOR over x1 , . . . , xr ).
Second, we will show that Z is a collection of pairwise independent RVs. Consider any S, U ⊆ [r]
such that S ̸= U and any a, b ∈ F2 . Then we have

Pr [ZS = a ∧ ZU = b] = Pr [ZS = a | ZU = b] Pr [Zu = b],

x1 ,...,xr ∼F2 x1 ,...,xr ∼F2 x1 ,...,xr ∼F2

and all we need is for Prx1 ,...,xr ∼F2 [ZS = a | ZU = b] = Prx1 ,...,xr ∼F2 [ZS = a]. Similarly as in
Example 2.2, since S ̸= U there are some xi ’s (namely, {xi }i∈S\U ) that change the value of ZS
Lecture 3: Aug 30, 2022 3

regardless of the value of ZU . Hence, because the {xi }i∈S\U can change the value of ZS to 0 or
1 equally likely, we see that the value of ZU does not influence the result of ZS , giving us that
Prx1 ,...,xr ∼F2 [ZS = a | ZU = b] = Prx1 ,...,xr ∼F2 [ZS = a], so

Pr [ZS = a ∧ ZU = b] = Pr [ZS = a | ZU = b] Pr [Zu = b]

x1 ,...,xr ∼F2 x1 ,...,xr ∼F2 x1 ,...,xr ∼F2

= Pr [ZS = a] Pr [Zu = b],

x1 ,...,xr ∼F2 x1 ,...,xr ∼F2

as desired.

While this example may seem like a forced generalization of the previous one, it amazingly
allows us to efficiently1 generate n pairwise independent variables on F2 from r = log(1 + n)
uniform bits. However, we aren’t creating randomness from nothing, since we quickly notice that
if we consider (Z1 , . . . , Zn ) as an element of Fn2 , then the support generated by our example only
has 2r = 2log(1+n) = n + 1 values in it (since this is how many possible inputs our algorithm takes),
yet |Fn2 | = 2n , so our support is exponentially smaller than that of a uniform distribution over Fn2 .
This sparsity of our pairwise independent distribution on Fn2 illustrates how much stronger regular
independence is.
Eventually, we will use this technique of blowing up randomness to help us de-randomize algo-
rithms, but first we will generalize this construction from RVs on F2 to RVs on larger domains. To
do this, we will introduce the useful notion of universal hash functions.

Definition 2.4 (Family of Universal Hash Functions). The collection H = {h : [N ] → [M ]} is a

family of universal hash functions (UHFs) if for all x, y ∈ [N ] and all a, b ∈ [M ] we have that
1
1. Prh∈H [h(x) = a] = M

1
2. Prh∈H [h(x) = a ∧ h(y) = b] = M2
.

Immediately, we see that we can construct a collection of pairwise independent RVs simply by
sampling h ∼ H and taking Xi = h(i) for i ∈ [N ], and that doing this sampling only requires
log(|H|) random bits (since this is how many bits it takes to enumerate the elements of H).
Now, of course, the question that remains is how to construct a family of UHFs efficiently.

Example 2.5 (Construction of a family of UHFs). Let N = 2n for some n ∈ N and fix our base
field as F2n (which, we recall, is isomorphic to Fn2 ), so N = |F2n |. To remain consistent with our
previous notation, it will be useful to view F2n as [N ]. We then sample c, d ∼ F2n and define a hash
function by the linear expression

hc,d : [N ] → [N ]
x 7→ cx + d

The collection H = {hc,d }c,d∈F2n is a family of UHFs that can be sampled with O(log N ) bits.

Proof. Take any x, y, a, b ∈ F2n such that x ̸= y. Note that to sample from H, all we need to do is
to sample c and d from F2n , which requires n + n = 2n = 2 log N = O(log N ) bits. Thus, using the
1
Here, by efficient we mean in terms of n. I.e., we have to compute n XOR values, each of which looks at
r = log(1 + n) bits, which in total takes n log(1 + n) = O(poly(n)) time.
Lecture 3: Aug 30, 2022 4

definition of hc,d , we can compute

Pr [h(x) = a ∧ h(y) = b] = Pr [hc,d (x) = a ∧ hc,d (y) = b]

h∈H c,d∼F2n

= Pr [cx + d = a ∧ cy + d = b]
c,d∼F2n
 
b−a bx − ay
= Pr c= ∧d= .
c,d∼F2n y−x x−y
b−a
But both y−x and bx−ay
x−y are just arbitrary, fixed elements of F2 , so the probability of c and d
n

1
hitting them is exactly N and are independent events, giving us that
 
b−a bx − ay
Pr [hc,d (x) = a ∧ hc,d (y) = b] = Pr c= ∧d=
c,d∼F2n c,d∼F2n y−x x−y
   
b−a bx − ay
= Pr c= Pr d= ,
c,d∼F2n y − x c,d∼F2n x−y
giving us that H is indeed a family of UHFs.

With this construction, we have shown the following claim.

Claim 2.6. There exists an efficient algorithm that takes 2 log N random bits and produces a
pairwise independent distribution on [N ].
Although we will not show it here, this can be generalized to hash functions with domain [N ]
and range [M ] while requiring log N + log M random bits. We will use this result shortly, so we
state it here as a lemma.
Lemma 2.7. There exists an efficient algorithm that takes log N + log M random bits and produces
a pairwise independent distribution on [M ].2
In comparison, if we attempted the naı̈ve approach of randomly picking a hash functions, one
would require N log N bits. Again, this shows how far pairwise independence is from (complete)
independence.

3 Pairwise Randomness and BPP

Now we circle back to the question we asked at the beginning of lecture, namely Question 1: Can we
construct another algorithm that uses less randomness than B to achieve the same 1 − ε error rate?
Recall our definition of B in Algorithm 1, where we sample r1 , . . . , rt i.i.d from {0, 1}poly(|x|) and
then take Maj(Y1 , . . . , Yt ) as our result where Yi = A(x, ri ). After introducing pairwise independent
RVs, a reasonable question would be what occurs when we take r1 , . . . , rt to be pairwise independent
instead of independent. Call this modification of B with pairwise independent samples B2 .
For consistency, since we can consider {0, 1}poly(|x|) as F2poly(|x|) , let R = 2poly(|x|) so that we may
again view F2poly(|x|) as [R]. With regular independence, to sample r1 , . . . , rt from [R] would require
t log R bits (since sampling each ri takes log R bits). On the other hand, applying Lemma 2.7 with
N = t and M = R gives us that we can sample pairwise independent r1 , . . . , rt from [R] only using
log t + log R random bits, many fewer than t log R.
2
For those wondering why we cannot just make N small and use few random bits to get a pairwise independent
distribution on [M ], recall that N is the number of elements that we have to be able to hash (i.e., the number of
pairwise independent variables that we want in the end).
Lecture 3: Aug 30, 2022 5

However, now that we have changed our sampling strategy for r1 , . . . , rt ∼ [R] from independent
to pairwise independent, it is reasonable to expect the value of t (the number of pairwise independent
variables that we wish to sample) to differ from that of Algorithm 1, where we had t = log 1ε . To
find a new value for t in B2 , we will perform a similar analysis as the one we originally did for B
and use a tail bound.
Take any L ∈ BPP and, without loss of generality, assume x ∈ L (the proof Ptin the other case
i
is symmetrical. Recall from Algorithm 1 that Yi = A(x, r ) and define Y = i=1 Yi . Then, the
probability that B2 is correct on x is
 
t
Pr [B2 (x) = L(x)] = Pr Y ≥ .
r1 ,...,rt ∼[R] r1 ,...,rt ∼[R] 2

Furthermore, by the linearity of expectation we see that

t
" #
X
E [Y ] = E Yi
r1 ,...,rt ∼[R] r1 ,...,rt ∼[R]
i=1
t
X
= E [Yi ]
r1 ,...,rt ∼[R]
i=1
2
≥ t,
3
where the last line follows from our definition of BPP. We now know that we want to avoid the
case that Y < 12 and that Er1 ,...,rt ∼[R] [Y ] ≥ 23 t, so we could reasonably ask for the probability of Y
t
being within 10 of its mean. In other words, we would like to upper bound3
 
2 t
Pr Y − t > . (1)
r1 ,...,rt ∼[R] 3 10

Previously, for B we used the Chernoff bound to (1), but in this case that is no longer an option
as the r1 , . . . , rt ∼ [R] are only pairwise independent. Instead, we will use Chebyshev’s inequality,
which requires us to compute Var(Y ). Thankfully, since the Yi ’s are pairwise independent (because
the ri ’s are), we have that Cov(Yi , Yj ) = 0 for i ̸=
j. Then sing the fact that each Yi is a Bernoulli
RV with p = 32 , meaning that Var(Yi ) = 23 1 − 23 = 92 , we can compute
t
!
X
Var(Y ) = Var Yi
i=1
t
X X
= Var(Yi ) + Cov(Yi , Yj )
i=1 i̸=j
t
X 2t
= Var(Yi ) ≤
9
i=1

We can now apply Chebyshev’s inequality to (1) as

 
2 t 100 2t c
Pr Y − t > ≤ 2 · =
1 t
r ,...,r ∼[R] 3 10 t 9 t
3
Upper bounding this value does also limit the probability that we are in the upper end of the tail, but this is an
acceptable relaxation as being near the mean of Y is sufficient in our case.
Lecture 3: Aug 30, 2022 6

Thus, to upper bound this value
by ε we need ct ≤ ε, so we choose t ≥ εc = Ω 1ε , meaning that B2

repeats A on the order of Ω 1ε times and uses log t + log R = log 1ε + log R + O(1) random bits.
Putting this together with the facts about B in Table 1 gives us

Algorithm Accuracy Runtime Randomness

B 1−ε c · T (n) · log 1ε c · R(n) log 1ε
B2 1−ε c′ · T (n) · 1ε R(n) + log 1ε + O(1)

Table 2: Accuracy, runtime, and randomness usage of B and B2 .

In conclusion, we have answered a definitive YES to Question 1, showing that we can indeed use
fewer random bits than B while achieving the same 1 − ε error rate. Nevertheless, this was at the
cost of an exponential increase in runtime. We can further explore this trade-off between runtime
and randomness by defining Bk to be analogous to the algorithm that we have been using, but with
the r1 , . . . , rt used in it drawn k-wise independently (where we define k-wise independence as any
collection of k RVs being independent, so pairwise independence is simply 2-wise independence).
These Bk ’s will essentially interpolate between B and B2 , and their runtime and randomness usage
can be analyzed similarly as to what we have done so far, although higher moment methods are
required as k increases.