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).