Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola
1 Lecture 1, Scribe: Chin Ho Lee
In this first lecture we begin with some background on pseudorandomness and then we move on to the study of bounded independence, presenting in particular constructions and lower bounds.
1.1 Background
Let us first give some background on randomness. There are 3 different theories:
(1) Classical probability theory. For example, if we toss a coin times then the probability of each outcome is the same, i.e., . However, intuitively we feel that the first outcome is less random than the second.
(2) Kolmogorov complexity. Here the randomness is measured by the length of the shortest program outputting a string. In the previous example, the program for the second outcome could be “print 011011100011”, whereas the program for the first outcome can be “print 01 six times”, which is shorter than the first program.
(3) Pseudorandomness. This is similar to resource-bounded Kolmogorov complexity. Here random means the distribution “looks random” to “efficient observers.”
Let us now make the above intuition precise.
Definition 1.[Pseudorandom generator (PRG)] A function is a pseudorandom generator (PRG) against a class of tests with error , if it satisfies the following 3 conditions:
(1) the output of the generator must be longer than its input, i.e., ;
(2) it should fool , that is, for every test , we have ;
(3) the generator must be efficient.
To get a sense of the definition, note that a PRG is easy to obtain if we drop any one of the above 3 conditions. Dropping condition (1), then we can define our PRG as . Dropping condition (2), then we can define our PRG as . Dropping condition (3), then the PRG is not as obvious to obtain as the previous two cases. We have the following claim.
Claim 2. For every class of tests , there exists an inefficient PRG with error and seed length .
Before proving the claim, consider the example where is the class of circuits of size over -bit input, it is known that . Hence, applying our claim above we see that there is an inefficient PRG that fools with error and seed length .
We now prove the claim using the probabilistic method.
Proof. Consider picking at random. Then by the Chernoff bound, we have for every test ,
if . Therefore, by a union bound over , there exists a fixed such that for every , the probabilities are within .
1.2 -wise independent distribution
A major goal in research in pseudorandomness is to construct PRGs for (1) richer and richer class , (2) smaller and smaller seed length , and making the PRG explicit. For starters, let us consider a simple class of tests.
Definition 3.[-local tests] The -local tests are tests that depend only on bits.
We will show that for this class of tests we can actually achieve error . To warm up, consider what happens when , then we can have a PRG with seed length by defining and .
For , we have the following construction. Define
Here the length of and is , and we exclude . Note that the output has bits, but we can append one uniform bit to the output of . So the seed length would be .
Now we prove the correctness of this PRG.
Claim 4. The defined above is a PRG against -local tests with error .
Proof. We need to show that for every , the random variable over the choice of is identical to , the uniform -bit string. Since , suppose without loss of generality that there exists an such that and . Now is uniform, and conditioned on , is also uniform, thanks to the index .
The case for becomes much more complicated and involves the use of finite fields. One can think of a finite field as a finite domain that behaves like in the sense that it allows you to perform arithmetic operations, including division, on the elements. We will use the following fact about finite fields.
Lemma 5. There exist finite fields of size , for every prime and integer . Moreover, they can be constructed and operated with in time .
Remark 6. Ideally one would like the dependence on to be . However, such construction remains an open question and there have been many attempts to constructing finite fields in time . Here we only work with finite fields with , and there are a lot of explicit constructions for that.
One simple example of finite fields are integers modulo .
Theorem 7. Let . For every , there exists an explicit construction over such that
(1) elements in can be sampled with bits, and
(2) every symbols are uniform in .
For , we can use the above theorem with , and the PRG can output the first bit of every symbol.
Remark 8. There exist other constructions that are similar to the inner product construction for the case , with carefully chosen, but the way to choose involves the use of finite fields as well.
Note that we can also apply the theorem for larger to fool -local tests with seed length .
We now prove the theorem.
Proof. Pick a finite field of size . Let be uniform random elements in which we think of as a polynomial of degree . We define the generator to be
(One should think of the outputs of as lines and curves in the real plane.)
The analysis of the PRG follows from the following useful fact: For every points , there exists exactly one degree polynomial going through them.
Let us now introduce a terminology for PRGs that fool -local tests.
Definition 9. We call distributions that look uniform (with error ) to -local tests -wise independent (also known as -wise uniform). The latter terminology is more precise, but the former is more widespread.
We will soon see an example of a distribution where every elements are independent but not necessarily uniform.
1.3 Lower bounds
We have just seen a construction of -wise independent distributions with seed length . It is natural to ask, what is the minimum seed length of generating -wise independent distributions?
Claim 10. For every , every PRG for -local tests over has seed length .
Proof. We use the linear-algebraic method. See the book by Babai–Frankl [1] for more applications of this method.
To begin, we will switch from to , and write the PRG as a matrix , where the rows are all the possible outputs of the PRG. Since the PRG fools -local tests and , one can verify that every columns of are orthogonal, i.e., for . As shown below, this implies that the vectors are independent. And by linear algebra this gives a lower bound on .
However so far we have not used . Here’s how to use it. Consider all the column vectors obtained by taking the entry-wise products of any of the vectors in . Because of -wise independence, these ’s are again orthogonal, and this also implies that they are linearly independent.
Claim 11. If are orthogonal, then they are linearly independent.
Proof. Suppose they are not and we can write for some . Taking inner product with on both sides, we have that the L.H.S. is nonzero, whereas the R.H.S. is zero because the vectors are orthogonal, a contradiction.
Therefore, the rank of must be at least the number of ’s, and so
Rearranging gives .
1.4 Who is fooled by -wise independence?
In the coming lectures we will see that -wise independence fools , the class of constant-depth circuits with unbounded fan-in. Today, let us see what else is fooled by -independence in addition to -local tests.
(1) Suppose we have independent variables and we want to understand the behavior of their sum . Then we can apply tools such as the Chernoff bound, tail bounds, Central Limit Theorem, and the Berry–Esseen theorem. The first two give bounds on large deviation from the mean. The latter two are somewhat more precise facts that show that the sum will approach a normal distribution (i.e., the probability of being larger than for any is about the same). One can show that similar results hold when the ’s are -wise independent. The upshot is that the Chernoff bound gives error , while under -wise independence we can only get an error .
(2) We will see next time that -wise independence fools and .
(3) -wise independence is also used as hashing in load-balancing.
1.4.1 -wise independence fools AND
We now show that -wise independent distributions fool the AND function.
Claim 12. Every -wise uniform distribution fools the AND functions on bits with error .
Proof. If the AND function is on at most bits, then by definition the error is . Otherwise the AND is over more than bits. Without loss of generality we can assume the AND is on the first bits. Observe that for any distribution , we have
The right-hand-side is the same under uniform and -wise uniformity, and is . Hence,
Instead of working over bits, let us now consider what happens over a general domain . Given functions . Suppose are -wise uniform over . What can you say about the AND of the outputs of the ’s, ?
This is similar to the previous example, except now that the variables are independent but not necessarily uniform. Nevertheless, we can show that a similar bound of still holds.
Theorem 13.[[2]] Let be random variables over , which are -wise independent, but not necessarily uniform. Then
This fundamental theorem appeared in the conference version of [2], but was removed in the journal version. One of a few cases where the journal version contains less results than the conference version.
Proof. Since each is in , by De Morgan’s law, we can write
If we define the event to be , then is the same as . Now we apply the inclusion-exclusion principle, which says
we will finish the proof in the next lecture.
References