In Combinatorial Descrepancy, Paul selects objects and Carole balances them into two piles as evenly as possible.

In this talk the objects will be n n-dimensional vectors with coefficients ±1. Carole assigns to each vector ±1 (the two piles) and the payoff (which Carole tries to minimize) is the L-infinity norm of the signed sum.

We consider four variants of this problem. Paul may play randomly (in which case Carole tries to minimize expectation) or adversarially. Carole may play On-Line (selecting each sign immediately after seeing its vector) or Off-Line (seeing all vectors and then selecting all signs).

The arguments (for both Paul and Carole) involve a combination of appropriate weight functions and probabilistic (Carole selects ±1 randomly!) thinking.

The four variants are all interesting. In each case we know the answer up to constants and in some cases we know (or nearly know) the constants.

We emphasize new results, with Nikhil Bansal, for the random on-line variant.

Anagram Fans!: Why is Carole spelled with an e?