Voting methods, Fourier analysis, and Gaussian geometry

12/05/2017 - 12:15pm
12/05/2017 - 1:10pm
Steven Heilman (UCLA and University of Notre Dame)

Given votes for candidates, what is the best way to determine the winner of the election, if some of the votes have been corrupted or miscounted? As we saw in Florida in 2000, where a difference of 537 votes determined the president of the United States, the electoral college system does not seem to be the best voting method. We will survey some recent answers to the above question along with some open problems. These results use tools from probability, from discrete Fourier analysis and from the geometry of the Gaussian measure on Euclidean space. Answering the above voting question reveals unexpected connections to Khot's Unique Games Conjecture in theoretical computer science and to the MAX-CUT problem and its variants. We will discuss these connections and present recent results and open problems.

Millikan 2099, Pomona College