#
Geometric discrepancy (An illustrated guide) by Jiri Matousek

### Some striking new developments in combinatorial discrepancy in 2010-11

- Bansal's algorithm for computing low-discrepancy
colorings, based on semidefinite programming, which makes
a number of bounds obtained by the partial coloring method
constructive.
- Hardness results of Charikar, Newman, and Nikolov:
it is hard to approximate
the combinatorial discrepancy with factor better than n^{1/2}.
- The discrepancy for 3 permutations is of order log n,
as a lower bound by Newman and Nikolov shows.

### A revised second printing is out (January 2010)

with known errors fixed, references updates,
and with a short appendix describing new developments.
The appendix plus the updated bibliography can be found
here.
## Errata for the second printing (2010)

- P.2, picture, the notation doesn't match the text above,
a_2 and b_1 should be interchanged. (Noted by Chris Lawton.)

## Errata for the first printing (1999)

- P. 16 Exercise 3, the first subscript 2 should be d.
- P. 21, 2nd line of the formula beginning with "eta=", the
sum should be from j=1.
- P.49 last line, the sum should be up to K-1, not K. (Noted by
Michael Gnewuch.)
- P.53 3rd line above Prop. 2.7, m_k should be m_d.
(Noted by Michael Gnewuch.)
- P.54, last line of Th. 2.9, box of volume b^{-m+q} instead of
b^{m-q}. (Noted by Michael Gnewuch.)
- P.60, bottom displayed formula, sgn^{pm}(b'_{t+1}-b_{t+1})
should be sgn^{pm}(b_{t+1}-b'_{t+1}), with the same swap once again
on the next page. (Noted by Michael Gnewuch.)
- P. 108 Exercise 1, missing factor (1/m) under the square root sign
(the inequality should read \disc_2(S) \ge \sqrt{(1/m)
\trace(D)}). (Noted by Benjamin Doerr.)
- P. 174 last line, the formulas for a and for b should be interchanged.
(Noted by Adrian Dumitrescu.)
- P. 178 bottom, a serious mistake in the proof of Baker [Bak]
was discovered by J. Beck. In 2008 Bilyk, Lacey, and
Vagharshakyan proved a better lower bound; see "New developments" below.
- P. 179 Exercise 2(a) is wrong. A counterexample was constructed
by Beck, and this is the flaw in Baker's proof mentioned
in the previous comment.
- P. 243, the lower bounds for D(n,R^d) and for disc(n,R^d)
should be changed according to the remark to page 178.
- Hint to Exercise 2.1.3: there are many points ON the diagonal x=y;
the empty rectangle should be taken near the diagonal but
not containing it.
- Hint to Exercise 4.1.1: (n-2\Delta)/(n+2\Delta) should
be (n-4\Delta)/(n+4\Delta), and consequently, the 12 later should
become 24. (Noted by Benjamin Doerr.)