All events are in Central time unless specified.

Joel Spencer, Courant Institute—New York University

Four Discrepancies

4:00 pm–4:50 pm
Avery Hall Room: 115 Avery Hall
Tri Lai ,
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?

Additional Public Info:
Hosted by Tri Lai

Download this event to my calendar

This event originated in Math Colloquia.