Colloquium
4:00 p.m., Monday (January 16, 2006)
MATH 105
Ryan O'Donnell
Microsoft
Noise stability, in elections and elsewhere
Although the Liberals probably have a lock on Vancouver Quadra, next
Monday we will see some close election results. With close outcomes
come recounts, and with recounts, we are led to the following
questions:
Suppose that in an election between two parties, the voters vote
independently and uniformly at random. Further suppose that there is
an automatic recount in which each vote is changed independently with
probability epsilon. What is the probability that the recount affects
the outcome of the election? And how does this change under different
voting systems (simple majority, electoral college, etc.)?
In this talk I will describe a new theorem showing that, in some
sense, simple majority is the voting system that is stablest under
recount noise. I will also discuss several applications of this
result, to such diverse fields as algorithmic complexity,
combinatorics, and metric space embeddings.
Refreshments will be served at 3:45 p.m. (MATX 1115, Math Lounge).
