“Everything is vitally connected, not merely artificially related, so that when I see anything, I am seeing everything. When I speak to anyone, I am speaking to everybody. When I touch anything, I touch all things, and when I know one thing, I know everything.” – Brihadaranyaka Upanishad
In this post, I’ll cover some of what I think are the coolest ideas in Vadhan’s survey, the principles unifying the main pseudorandom objects studied. We will continue where we left off in the last post by illustrating a connection between list encoding expanders. We then introduce the concept of randomness extractors and relate these to hash functions, expanders, and list encoding.
NOTE: This post only touches the surface on what Vadhan covers here.
List Encoding and Expanders
For , a target subset , and probability parameter , define to be the set of for which . Likewise, for a “filtering” function , define to be the set of for which . Taking to be the characteristic function on , we get .
As a sanity check, taking for a given encoding to be given by , where denotes the bits of given by and where we view as , we readily get out another definition for list-decodability:
Result 1: For an , define to be the set of all pairs for . Then the encoding is -list decodable iff for all .
Now taking to be the neighbor function for a -regular bipartite graph with left vertices and right vertices, i.e. so that is the th neighbor of left-vertex , we readily get another definition of vertex expansion in the case that only sets of exactly vertices expand- we will refer to such graphs as -vertex expanders:
Result 2: with neighbor function is an -vertex expander iff for every set of fewer than right-vertices, .
With these connections in mind, we proceed to prove that we can get a very good expander, albeit with nonconstant degree, out of a Parvaresh-Vardy code.
For the -ary Parvaresh-Vardy code of degree , redundancy , irreducible , and power , consider the -regular bipartite graph with left vertices indexed by and right vertices indexed by , with neighbor function given by .
Result 3: is an -expander.
Proof: We will tune the parameters for maximum set size and expansion as we go. We will first prove that is an expander. For this, result 7 tells us that we want to show that for all of cardinality less than .
The gist of the proof is essentially the same as our proofs of efficient list-decodability: we will find a “characteristic” polynomial that all elements of solve, then observe that the roots of include all elements of . Once we have shown that is an expander, we can tweak our proof to get expansion for all sets of cardinality less than as well.
Take polynomial of degree less than in and less than in each of the other variables. We want to be solved by all elements in , so as long as the number of unknowns exceeds the number of constraints . So it’ll be convenient to take . As usual, we’ll assume that has no factors of .
Now we want that for every that , but this is already true for all choices of . In order for this univariate polynomial in to be the zero polynomial, we’d like that the number of these roots exceeds the degree of the polynomial, so let’s take to be . With this in mind, we can simply factorize the polynomial to get our elements . In particular, the number of such elements is bounded above by the degree of in , which is as desired.
We can easily tweak the above argument to work for smaller values of than : build our out of monomials where and (instead of , where is the monomial of degree in so that . By construction, our bound for the existence of such a still holds, and the degree of that bounds the cardinality of is still strictly bounded above by .
By picking our parameters , , , carefully, we get a remarkably good expander.
Result 4: For all , maximum subset size , , and tradeoff parameter , there exists a fully explicit , expander with left-vertices, left-degree , and right vertices.
Proof: Because the number of left vertices is , we take to be . The number of right-vertices is . We’d like to be close to where . Take to be something (we’ll specify this later) in , and take to thus be , and this will give us the desired upper bound on . To get the desired expansion factor, we must show that . But and , so taking gives the desired lower bound on expansion. By this choice of , we also get the desired asymptotic growth for left-degree .
What remains is to choose an appropriate . We want an explicit expander, so taking to be a power of 2 allows us to describe the field we’re working with in time polynomial in and , completing the proof.
Note that the parameter gives a tradeoff between the size of the right half of the graph and the size of its left-degree. More importantly, we get arbitrarily-close-to-optimal expansion at the cost of polylogarithmic degree.
Randomness Extractors – Preliminaries
We now introduce the notion of randomness extractors. Morally, these will be maps which smear “weakly random” variables into variables whose distributions are pretty close to perfectly random. These will be helpful both in running BPP algorithms using weakly random sources of bits, say atmospheric radio noise or the low-order bits of the system clock. Formally, a source on will denote a random variable taking values in . We’ll first need a notion of statistical “closeness”:
Definition 1: Two random variables on have statistical difference given by , where the maximum is taken over all subsets of . If , we say that and are -close.
It turns out this condition is equivalent to the following:
Definition 1’: , where here denotes the norm.
With this in mind, we can define a simple class of extractors:
Definition 2: A map is a deterministic -extractor for a class of sources if is -close to the uniform distribution over for all sources .
We will restrict our attention to sources which we know contain at least a certain amount of randomness.
Definition 3: A -source is a random variable such that for all . In other words, a -source has min-entropy bounded below by .
It turns out that for any -source, random functions are good extractors. To prove this, it suffices to prove these for the “basis elements” of the class of -sources, so we begin with a lemma and a definition.
Definition 4: The flat -source on for is the uniform distribution on .
Lemma 1: Every -source on is a linear combination of flat -sources , where .
Proof: The picture is of a circle broken up into half-open intervals of length . Pick a collection of points evenly spaced around the circle. Because is a -source, each contains at most one point of , and let denote the set of such that contains a point. Picking a point from where is a randomly chosen rotation of gives with probability . Then .
Then we get the following out of the Chernoff bound given in a previous post.
Result 5: For every , every flat -source , and every error parameter , a randomly chosen function for is a deterministic extractor for with probability .
Unfortunately, we can’t find extractors that work for all -sources.
Result 6: There are -sources for which there exist no deterministic -extractors for arbitrarily small .
Proof: Specifically, even for any map , we can easily construct an -source for which is constant. The image of hits 0 and/or 1 at least times, so the uniform distribution on the preimage of this bit is our desired -source.
Morally, the reason for this is that there are too many flat -sources. To get around can loosen our deterministic definition by introducing a purely random seed:
Definition 5: A function is a extractor of seed if for any -source on , is -close to .
Now we can show (nonconstructively) that there are extractors that work for all -sources, provided we use a long enough random seed.
Result 7: For all , there is an -extractor of seed with image in for .
Proof: Again, we just need to show that there is an extractor that maps all flat -sources -close to . We want to show that the probability that a random extractor fails to do this is below 1. By the union bound and the previous result for deterministic extractors, we get an upper bound on the probability of failure of for , and Stirling’s approximation gives an upper bound of , and tuning the parameters to make this upper bound less than 1 gives the desired bound on seed length.
Having motivated seeded extractors, we now proceed to give a straightforward connection between extractors and expanders and then a result due to Impagliazzo, Levin, and Luby relating extractors to hash functions.
Extractors and Expanders
The signature of any given seeded extractor is highly suggestive of a neighbor function for a bipartite -regular graph which we will denote by , with left vertices and right vertices. The th neighbor of vertex in is .
It turns out that we can translate the condition of being a -extractor into something beautifully (and usefully) reminiscent of the Expander Mixing Lemma:
Result 8: is an -extractor iff satisfies, for every set of left-vertices and every set of right-vertices ,
Proof: The condition for a function to be a -extractor is that for every flat -source and , we have
We can translate into the probability that an edge leaving in is in the cut from to , i.e. . Likewise, we can translate to the probability that a right vertex lies in , i.e. , and we get the desired result.
This result tells us we can import results on spectral expanders to constructions of extractors. In particular, by taking the on the right-hand side of the Expander Mixing Lemma to be at most , it suffices to take a spectral expander with expansion .
Applying this to a Ramanujan graph, i.e. one of optimal spectral expansion , we find when we solve for that taking the corresponding extractor gives a -extractor with an output of .
Extractors and Hash Functions
The connection between hash functions as considered in a previous post about random-efficient error reduction and extractors is equally evocative: an extractor for the flat -sources for set can be thought of as a hash function that maps almost uniformly to its image. We have the following result due to Impagliazzo, Levin, and Levin saying that if we use the purely random bits needed to choose a hash function out of a pairwise independent family, we get a good seeded extractor.
Result 9 (Leftover Hash Lemma) The map for given by is a -extractor, where is a hash function taken from the pairwise independent family .
Proof: Take to be any -source and to be the random variable uniformly distributed on the family . The key is to recall the alternative definition of statistical difference in terms of the -norm and show that the collision probability, which is closely related to the -norm, of is close to .
Recall that . We have a collision of when the hash functions agree and when either the ’s agree or they disagree but are hashed to the same value. This occurs with probability at most . So the -norm of the difference is bounded above by .
Cauchy-Schwarz tells us that the ratio of the -norm to the -norm is bounded above by , where is the dimension of the underlying vector space, so the statistical difference between and is bounded above by , so we’re done.
The result gets its name from the fact that morally, this result says that if an adversary has acquired a certain number of bits of a secret key of ours, we can still create a key out of the remaining bits of which the adversary has very little knowledge.
List Encoding and Randomness Extractors
Lastly, we place randomness extractors under this unifying framework of list-decodability. Our will be our extractor .
Result 10a: If is a -extractor, then for all , .
Proof: Say that and let be the -source uniformly distributed on . Then by construction the expected value of is more than , implying that and are -far, a contradiction!
There is a “converse” that involves coarser functions which only take discrete bit values (for this reason, we will consider the set formulation of instead), more entropy, and more error; these turn out to be insignificant for extractors.
Result 10b: If for every we have that , then is a .
Proof: lies in either if falls in or if it doesn’t and anyways, where is any -source. Some calculation tells us that and are indeed -close.
We conclude with an explicit connection between list encoding and extractors. The extractor corresponding to an encoding is . One direction of correspondence we get just out of the parallel between the list-decoding formulation of list-decodability and randomness extractors:
Result 11a: If is a -extractor, then is -list decodable.
There is again a slightly worse converse which says that in the other direction, the error blows up unless the alphabet of our code is small.
Result 11b: If is -list decodable, then is a -extractor.
Proof: Take a -source and the uniform distribution over . We want to show that and are -close. The statistical difference is equal to the expected value of taken over all from , and the definition of statistical difference tell us this is bounded above by , and by list decodability, defining to be the set of where is the choice that maximizes the probability in this expression, we find the statistical difference is bounded above by . We can split this probability up into the cases that lies or does not lie in , and then a bit of computation gives us the desired -closeness.