According to the preface, discrepancy theory asks how uniform a sequence of numbers can be. In more detail, it asks how fast, for a sequence {Xi}, the function D(n) = sup{|{i | Xi ≤ X & i ≤ n}| - nX|} can grow with n, where sup is taken over all X in [0,1]. This idea can be extended to domains other than sequences of numbers, such as set systems and range spaces. The discrepancy method described in this text applies tools from discrepancy theory to complexity theory and algorithm design in such diverse areas as probabilistic algorithms, communication complexity, computational geometry, and derandomization.

The first three chapters outline the basics of discrepancy theory. If there is a set system and a red-blue coloring of the domain, then the discrepancy for that coloring is the maximum over all the sets of the absolute difference between the number of reds and blues. The discrepancy of the system is the minimum for all colorings. Alternatively, an L2 norm can be used where the discrepancy of a coloring is defined using the root mean square rather than maximum value. These notions can also be defined in terms of the incidence matrices representing the set system. In chapter 1, it is established for a set system with domain of size n and number of set m, the discrepancy is of order √nlog(m) and if the number of sets is O(n) then the discrepancy is O(√n). Some lower bounds are derived using spectral techniques and the incidence matrices.

Chapters 2 and 3 are concerned with upper-bound and lower-bound techniques respectively. In chapter 2, several methods are presented for constructing low-discrepancy point sets, and low-discrepancy properties of arithmetic progressions are investigated. Many diverse topics are touched upon here. There is even a section on the Shimura-Taniyama conjecture. The chapter concludes with a study of the problem of giving a set of points a red-blue coloring so that in any half-space, the sizes of the two colorings do not differ much. In chapter 3, many techniques for finding discrepancy lower bounds are employed including orthogonal functions, Fourier transforms, Riesz products, finite differences, and so on. For example, finite differences are used to obtain lower bounds on the red-blue discrepancy of half-spaces.

Chapter 4 is about sampling: obtaining representative samples from large data sets. The question asked regards how to approximate some parameter by only using a small sample from the whole set. The important tools used are &egr;-nets and &egr;-approximations.

The next chapter covers geometric searching. Here, a data structure called an &egr;-cutting is introduced, which allows a problem to be broken into smaller sub-problems, leading to divide and conquer algorithms. Applications for point location in a hyperplane and simplex range searching are presented.

Chapter 6 is about complexity lower bounds, and a theme is that high discrepancy implies high complexity, and the link is via the spectrum of the incidence matrix. Problems concerning arithmetic circuits (monotone and non-monotone) and geometric databases are studied. In chapter 7, an optimal convex hull algorithm is designed, making use of many of the tools introduced in earlier chapters. This is followed by a short chapter on linear programming.

Chapter 9 discusses the topic of pseudorandomness. Attention is then turned to communication complexity in chapter 10. The communication complexity of the inner product is first discussed, followed by a development of a communication complexity game to derive lower bounds for searching.

The last chapter is on minimum spanning trees (MST). Low-discrepancy sampling is achieved using an approximate priority queue called a soft heap. This then leads to a deterministic algorithm with n vertices and m nodes, where a is the inverse Ackermann function. This is the only chapter which contains any real code fragments.

There are three appendices giving further mathematical background on probability theory, harmonic analysis, and convex geometry, which will be useful for computer scientist readers.

The book ends rather abruptly, and I think it would have been advantageous to have a concluding chapter summarizing what has been achieved.

The text is well written, and the author’s enthusiasm is evident. It is aimed at the graduate student or researcher who enjoys theoretical computer science. The chapters are broken up into numerous subsections and diversions, which cover a great variety of mathematical topics, from probability theory and modular functions to elliptic functions. The end of each chapter contains bibliographic notes placing the material in context, which is very useful. This is a unique book, and an important source for anyone who wants to find out about the discrepancy method. It is mathematically rigorous and, as a result, can be quite demanding at times.