Before sketching important elements of this book, it may be useful to potential readers for me to make a few general observations. This monograph is in the European Association for Theoretical Computer Science (EATCS) monograph series. It is an edited version of the author’s PhD thesis.

The book consists of five chapters. The second and fifth chapters are mainly combinatorial in flavor, and chapters three and four are algebraic. The intricate multi-parameter mappings (typical of probabilistic constructions) lead to a wealth of notation, so a table of contents, or at least a glossary, would have been helpful. Gabizon repeats definitions across chapters, and perhaps a less episodic structure might have emerged from editing.

This review gives brief accounts of chapters 1 through 4 by highlighting observations, methods, and results that seemed especially interesting. It is also worth mentioning that the book presents probability arguments and methods quite clearly, and in a way that readers can study them separately. Finally, the book contains two very useful appendices, one on probability methods and the other on concepts from algebraic geometry.

Chapter 1 introduces the concept of an extractor, E : {0,1}ⁿ → {0,1}^m. For a class of probability distributions on {0,1}ⁿ and for X ∈ , the distribution E(X) on {0,1}^m is computed by drawing samples x from X and computing E(X). The idea is that E(X) is supposed to be a class of the uniform distribution on {0,1}^m. The min-entropy of X is defined to be min_{x ∈ {0,1}ⁿ} log (1/pr(x)), where pr(x) is the probability assigned to x by X. Note that the uniform distribution has min-entropy n. The classes consist of weak random sources in that the min-entropy of X ∈ will generally be much smaller than n. The chapter includes examples of these classes.

One can modify the extractor definition to deal with this constraint by admitting random seeds (short strings) via E : {0,1}ⁿ × {0,1}d → {0,1}^m, where seeds come from {0,1}^d.

Chapter 2 explores details of this modification. One interesting point that the author brings out is the partially antagonistic relationship between his extraction results and results from finite Ramsey theory. This chapter contains results on extractors over bit-fixing distributions. X is k bit-fixing if bits i₁, &ellip; ,i_k ∈ {1,&ellip; ,n} are uniformly distributed over {0,1}^k and the remaining n-k bits of X are fixed. The main results, Theorems 2.1 and 2.2, establish quantitative bounds for m (the extractor output) and the error (closeness of the extractor distribution to uniform) in terms of k. Both results require lower bounds on k in terms of n. I highlight two:

• A remark on using O(log log n) random bits to partition{1, &ellip; n} into log^{O(1)} n sets T₁ ,&ellip; ,_r such that for any k element S ⊆ {1,&ellip; ,n}, withprobability 1 - O(log n), each T_i ∩ S has roughly k elements.
• Section 2.2.2 has several useful probability results.

Chapter 3 deals with extractors for a class of distributions over finite fields. As usual, denotes the n-dimensional vector space (affine space) over the finite field with q elements. The class, , an affine (n, k)_q source, is defined as follows. X ∈ is sampled by choosing t₁ ,&ellip; ,t_k ∈ uniformly and independently and computing b + ∑_{j=1}^k t_j ^˙ a_j, where a₁ ,&ellip; , a_k, b ∈ _{q}ⁿ and a₁ ,&ellip; , a_k are linearly independent. That is, X is a random affine mapping from _{q}ⁿ to _{q}^k. As in chapter 2, a closeness parameter (called error) is introduced to measure the distance of an extractor from the uniform distribution. There are two principal theorems. I cite the first because it illustrates the main idea of the chapter.

[Thm. 3.1]
There exists a constant q₀ such that for any _{q}ⁿ with q > max{q₀, n²⁰}, there exists an affine source extractor D: _{q}ⁿ → _{q}^k-1 with error ρ ≤ 1/q^{1/21}.

Here are two highlights of the chapter:

• Discussion (3.3.2) of characters for finite fields. (The definition of the trace could be better motivated.) These results may be of interest to researchers in algebraic geometry over finite fields.
• Section 3.5 details extractor construction for the (n, 1)_q case. (One-dimensional affine subspaces are called lines.)

Chapter 4 presents results on extractors for polynomial sources. The machinery here is a low-degree multivariate polynomial over _q. As the author points out, the material on algebraic geometry is of considerable independent interest. The chapter compares affine sources to polynomial sources with respect to min-entropy. An important connection also exists between the min-entropy of a polynomial source and the rank of its Jacobian. A polynomial source is a mapping x: _q^k → _qⁿ given by x(t₁ , &ellip; , k) = (x₁ (t₁ , &ellip;, tk), &ellip;, x_n (t₁ , &ellip;, t_k)), where each x_i (t₁, &ellip;, t_k) is a k-variate polynomial over . The Jacobian of x is the n × k matrix whose ij entry is . The rank of x, rank(x), is defined to be the rank of the Jacobian of x. The author shows that for a suitable bound on the total degree d of x, the min-entropy of a polynomial source equals rank(x) ^˙ log ||.

Here are some highlights of the chapter:

• Section 4.2.3 has results on the number of solutions of a system of polynomial equations over finite fields.
• Section 4.3 contains a connection between rank and algebraic independence (maximal rank for x).
• Section 4.4 contains classical but highly useful facts on determinants.
• Section 4.5.1 has material drawn from algebraic geometry concerning intersection of varieties (see also Appendix B).