Outside Event: Hovde Distinguished Lecture Series: Moses Charikar

Join the College of Science for the 2024-25 Hovde Distinguished Lecture Series featuring, Moses Charikar professor and computer scientist from Stanford University. He will present “How to appease a majority?” at 3:00 P.M. on Wed Mar 26 in the Hall of Data Science and AI, room 1069. A reception will follow at 4:00 P.M.

The Hovde Distinguished Lecture Series exemplifies the core principles established by Purdue University President Frederick L. Hovde, whose legacy was built on a commitment to excellence in both teaching and research. From his very first address to the faculty in January 1946, Hovde emphasized that education and the extension of human knowledge through research were twin pillars of Purdue’s mission, believing that one could not thrive without the other. He insisted that first-class teaching and research were mutually dependent, setting a standard for academic rigor that continues to inspire today.

How to Appease a Majority?

Abstract

In 1785, Condorcet established a frustrating property of elections and majority rule: it is possible that, no matter which candidate you pick as the winner, a majority of voters will prefer someone else. You might have the brilliant idea of picking a small set of winners instead of just one, but how do you avoid the nightmare scenario where a majority of the voters prefer some other candidate over all the ones you picked? How many candidates suffice to appease a majority of the voters?

In this talk, I will answer this question. Along the way, we will roll some dice — both because the analysis involves randomness and because of a connection to the curious phenomenon of intransitive dice, that has delighted recreational and professional mathematicians alike, ever since Martin Gardener popularized it in1970.

Joint work with Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta and Kangning Wang.

Bio

Moses Charikar is the Donald E. Knuth professor of Computer Science at Stanford University. He obtained his PhD from Stanford in 2000, spent a year in the research group at Google, and was on the faculty at Princeton from 2001-2015.
His research interests include: efficient algorithmic techniques for processing, searching and indexing massive high-dimensional data sets; efficient algorithms for computational problems in high-dimensional statistics and optimization problems in machine learning; approximation algorithms for discrete optimization problems with provable guarantees; convex optimization approaches for non-convex combinatorial optimization problems; low-distortion embeddings of finite metric spaces.
He won the best paper award at FOCS 2003 for his work on the impossibility of dimension reduction, the best paper award at COLT 2017, the 10 year best paper award at VLDB 2017 and the 20 year test of time award at STOC 2022. He was jointly awarded the 2012 Paris Kanellakis Theory and Practice Award for his work on locality sensitive hashing, was named a Simons Investigator in theoretical computer science in 2014, and an ACM Fellow in 2021.