Moses Charikar

About

Moses Charikar is the Donald E. Knuth professor of Computer Science at Stanford University. He obtained his PhD from Stanford in 2000 and has a background that includes a year in the research group at Google and faculty experience at Princeton from 2001 to 2015. His research interests encompass efficient algorithmic techniques for processing, searching, and indexing massive high-dimensional data sets; algorithms for high-dimensional statistics and machine learning optimization problems; approximation algorithms for discrete optimization problems with provable guarantees; convex optimization approaches for non-convex combinatorial optimization problems; and low-distortion embeddings of finite metric spaces. His work has been recognized with several awards, including best paper awards at FOCS 2003, COLT 2017, and SODA 2024, 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, named a Simons Investigator in theoretical computer science in 2014, and became an ACM Fellow in 2021.

Research topics

• Computer Science
• Ecology
• Biology
• Theoretical computer science
• Mathematics
• Geography
• Mathematical optimization

Selected publications

• Distributed algorithms from arboreal ants for the shortest path problem

  Proceedings of the National Academy of Sciences · 2023 · 11 citations

  Senior authorCorresponding

  Colonies of the arboreal turtle ant create networks of trails that link nests and food sources on the graph formed by branches and vines in the canopy of the tropical forest. Ants put down a volatile pheromone on the edges as they traverse them. At each vertex, the next edge to traverse is chosen using a decision rule based on the current pheromone level. There is a bidirectional flow of ants around the network. In a previous field study, it was observed that the trail networks approximately min…

  DOI

• Breaking the Metric Voting Distortion Barrier

  Society for Industrial and Applied Mathematics eBooks · 2024-01-01 · 10 citations

  book-chapter1st authorCorresponding

  We consider the following well studied problem of metric distortion in social choice. Suppose we have an election with n voters and m candidates who lie in a shared metric space. We would like to design a voting rule that chooses a candidate whose average distance to the voters is small. However, instead of having direct access to the distances in the metric space, each voter gives us a ranked list of the candidates in order of distance. Can we design a rule that regardless of the election insta…

  PublisherDOI

• Breaking the Metric Voting Distortion Barrier

  Journal of the ACM · 2024-09-20 · 4 citations

  article1st authorCorresponding

  We consider the following well-studied problem of metric distortion in social choice. Suppose that we have an election with n voters and m candidates located in a shared metric space. We would like to design a voting rule that chooses a candidate whose average distance to the voters is small. However, instead of having direct access to the distances in the metric space, the voting rule obtains, from each voter, a ranked list of the candidates in order of distance. Can we design a rule that, rega…

  PublisherDOI

• Six Candidates Suffice to Win a Voter Majority

  2025-06-15 · 1 citations

  articleOpen access1st authorCorresponding

  A cornerstone of social choice theory is Condorcet’s paradox which says that in an election where n voters rank m candidates it is possible that, no matter which candidate is declared the winner, a majority of voters would have preferred an alternative candidate. Instead, can we always choose a small committee of winning candidates that is preferred to any alternative candidate by a majority of voters?<br/>Elkind, Lang, and Saffidine raised this question and called such a committee a Condorcet w…

  PublisherOA PDFDOI

• Approximately Dominating Sets in Elections

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapter1st authorCorresponding

  Condorcet’s paradox is a fundamental result in social choice theory which states that there exist elections in which, no matter which candidate wins, a majority of voters prefer a different candidate. In fact, even if we can select any \(k\) winners, there still may exist another candidate that would beat each of the winners in a majority vote. That is, elections may require arbitrarily large dominating sets.

  PublisherDOI

Recent grants

• AF: Small: Approximation Techniques for Combinatorial Optimization

  NSF · $400k · 2012–2015

• ITR Collaborative Research: ASE-DMC Computational Complexity of Interactive Computation

  NSF · $694k · 2004–2009

• AF: Small: Mathematical Programming Methods in Approximation

  NSF · $500k · 2009–2013

Frequent coauthors

• Sudipto Guha

  University of Pennsylvania

  34 shared

• Howard Karloff

  New York Proton Center

  33 shared

• Ashish Goel

  32 shared

• Prabhakar Raghavan

  29 shared

• Uriel Feige

  28 shared

• David B. Shmoys

  Cornell University

  27 shared

• Cristina G. Fernandes

  25 shared

• Jiri Sgall

  Laboratoire de l'Informatique du Parallélisme

  25 shared

Labs

• Student Success and Engagement TeamPI

Education

• Ph.D., Computer Science

  Stanford University

  1994

• M.S., Computer Science

  Stanford University

  1991

• B.S., Computer Science

  University of California, Berkeley

  1989

Awards & honors

• best paper awards at FOCS 2003, COLT 2017 and SODA 2024
• 10 year best paper award at VLDB 2017
• 20 year test of time award at STOC 2022
• Paris Kanellakis Theory and Practice Award (2012)
• Simons Investigator in theoretical computer science (2014)

Similar researchers at Stanford University

• Thomas Blom Hansenh-25