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

• 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

• Embedding Probability Distributions into Low Dimensional ℓ₁: Tree Ising Models via Truncated Metrics

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

  book-chapter1st authorCorresponding

  Given an arbitrary set of high dimensional points in ℓ1, there are known negative results that preclude the possibility of always mapping them to a low dimensional ℓ1 space while preserving distances with small multiplicative distortion. This is in stark contrast with dimension reduction in Euclidean space (ℓ2) where such mappings are always possible. While the first non-trivial lower bounds for ℓ1 dimension reduction were established almost 20 years ago, there has been limited progress in understanding what sets of points in ℓ1 are conducive to a low-dimensional mapping.

  PublisherDOI

• Approximately Dominating Sets in Elections

  ArXiv.org · 2025-04-29

  preprintOpen access1st 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. We show that approximately dominating sets of constant size always exist. In particular, for every $\varepsilon > 0$, every election (irrespective of the number of voters or candidates) can select $O(\frac{1}{\varepsilon ^2})$ winners such that no other candidate beats each of the winners by a margin of more than $\varepsilon$ fraction of voters. Our proof uses a simple probabilistic construction using samples from a maximal lottery, a well-studied distribution over candidates derived from the Nash equilibrium of a two-player game. In stark contrast to general approximate equilibria, which may require support logarithmic in the number of pure strategies, we show that maximal lotteries can be approximated with constant support size. These approximate maximal lotteries may be of independent interest.

  PublisherOA PDFDOI

• 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 winning set. They showed that winning sets of size 2 may not exist, but sets of size logarithmic in the number of candidates always do. In this work, we show that Condorcet winning sets of size 6 always exist, regardless of the number of candidates or the number of voters. More generally, we show that if α/1 − lnα ≥ 2/k + 1, then there always exists a committee of size k such that less than an α fraction of the voters prefer an alternate candidate. These are the first nontrivial positive results that apply for all k ≥ 2.<br/>Our proof uses the probabilistic method and the minimax theorem, inspired by recent work on approximately stable committee selection. We construct a distribution over committees that performs sufficiently well (when compared against any candidate on any small subset of the voters) so that this distribution must contain a committee with the desired property in its support.

  PublisherOA PDFDOI

• Metric Distortion for Tournament Voting and Beyond

  ArXiv.org · 2025-05-19

  preprintOpen access1st authorCorresponding

  In the well-studied metric distortion problem in social choice, we have voters and candidates located in a shared metric space, and the objective is to design a voting rule that selects a candidate with minimal total distance to the voters. However, the voting rule has limited information about the distances in the metric, such as each voter's ordinal rankings of the candidates in order of distances. The central question is whether we can design rules that, for any election and underlying metric space, select a candidate whose total cost deviates from the optimal by only a small factor, referred to as the distortion. A long line of work resolved the optimal distortion of deterministic rules, and recent work resolved the optimal distortion of randomized (weighted) tournament rules, which only use the aggregate preferences between pairs of candidates. In both cases, simple rules achieve the optimal distortion of $3$. Can we achieve the best of both worlds: a deterministic tournament rule matching the lower bound of $3$? Prior to our work, the best rules have distortion $2 + \sqrt{5} \approx 4.2361$. In this work, we establish a lower bound of $3.1128$ on the distortion of any deterministic tournament rule, even when there are only 5 candidates, and improve the upper bound with a novel rule guaranteeing distortion $3.9312$. We then generalize tournament rules to the class of $k$-tournament rules which obtain the aggregate preferences between $k$-tuples of candidates. We show that there is a family of deterministic $k$-tournament rules that achieves distortion approaching $3$ as $k$ grows. Finally, we show that even with $k = 3$, a randomized $k$-tournament rule can achieve distortion less than $3$, which had been a longstanding barrier even for the larger class of ranked voting rules.

  PublisherOA PDFDOI

• An Improved Greedy Approximation for (Metric) k-Means

  2025-12-14

  article1st authorCorresponding

  Clustering is a basic task in data analysis and machine learning, and the optimization of clustering objectives are well-studied optimization problems; amongst these, the k Means objective is arguably the most well known. Given a collection of points in a metric space, the goal is to partition them into k clusters, each with an associated center, so as to minimize the sum of squared distances of points to their cluster centers. In this paper, we present a polynomial-time $3+2 \sqrt{2}+\varepsilon{\lt}5.83$-approximation algorithm for k-Means in general metrics. This substantially improves on the current-best $(9+\varepsilon)$-approximation in [Ahmadian, Norouzi-Fard, Svensson, Ward - FOCS’17, SICOMP’20], and even slightly improves on the 5.92-approximation in [Cohen-Addad, Esfandiari, Mirrokni, Narayanan - STOC’22] for the Euclidean special case. A natural approach for k-Means is to leverage Lagrangian Multiplier Preserving (LMP) approximations for the facility location problem. The previous best results for k-Means build upon an adaptation of an LMP 3-approximation for facility location with metric connection costs in [Jain, Vazirani J.ACM’01] based on a primal-dual method, rather than on the improved LMP greedy 2-approximation for the same problem in [Jain, Mahdian, Markakis, Saberi, Vazirani - J.ACM’03]. The barrier to using the improved LMP algorithm was that no adaptation of this algorithm and its analysis to the case of squared metric connection costs was known (since squared distances violate triangle inequality). Our main contribution is overcoming this barrier by providing such an adaptation. This new LMP approximation algorithm is then combined with the framework recently introduced in [Cohen-Addad, Grandoni, Lee, Schwiegelshohn, Svensson - STOC’25] for the related (metric) k Median problem.

  PublisherDOI

• Pareto-optimal Non-uniform Language Generation

  ArXiv.org · 2025-10-03

  preprintOpen access1st authorCorresponding

  Kleinberg and Mullainathan (2024) recently proposed an interesting model for language generation in the limit: Given a countable collection of languages, and an adversary enumerating the strings of some language $L$ from the collection, the objective is to generate new strings from the target language, such that all strings generated beyond some finite time are valid. Li, Raman and Tewari (2024) and Charikar and Pabbaraju (2024) showed strong non-uniform generation guarantees in this model, giving algorithms that generate new valid strings from $L$ after seeing a number of distinct input strings $t(L)$ that depends only on $L$ (and the collection), but not the enumeration order. However, for both these works, the language-wise generation times $t(L)$ of the algorithm can be strictly sub-optimal. In this work, we study Pareto-optimality of non-uniform language generation in the limit. We propose an algorithm, whose generation times $t^\star(L)$ are (almost) Pareto-optimal: any other algorithm whose generation time for some language $L$ is strictly smaller than $t^\star(L)$, must satisfy that its generation time for some other language $L'$ is strictly worse than $t^\star(L')$. Pareto-optimality is essentially the best that one can achieve for non-uniform generation. Our algorithmic framework conveniently adapts to further give Pareto-optimal non-uniform generation algorithms in the practically motivated settings of noisy as well as representative generation.

  PublisherOA PDFDOI

• Metric Distortion for Tournament Voting and Beyond

  2025-07-02

  articleOpen access1st authorCorresponding

  In the well-studied metric distortion problem in social choice, we have voters and candidates located in a shared metric space, and the objective is to design a voting rule that selects a candidate with minimal total distance to the voters. However, the voting rule has limited information about the distances in the metric, such as each voter's ordinal rankings of the candidates in order of distances. The central question is whether we can design rules that, for any election and underlying metric space, select a candidate whose total cost deviates from the optimal by only a small factor, referred to as the distortion.

  PublisherOA PDFDOI

• A Characterization of List Language Identification in the Limit

  ArXiv.org · 2025-11-06

  preprintOpen access1st authorCorresponding

  We study the problem of language identification in the limit, where given a sequence of examples from a target language, the goal of the learner is to output a sequence of guesses for the target language such that all the guesses beyond some finite time are correct. Classical results of Gold showed that language identification in the limit is impossible for essentially any interesting collection of languages. Later, Angluin gave a precise characterization of language collections for which this task is possible. Motivated by recent positive results for the related problem of language generation, we revisit the classic language identification problem in the setting where the learner is given the additional power of producing a list of $k$ guesses at each time step. The goal is to ensure that beyond some finite time, one of the guesses is correct at each time step. We give an exact characterization of collections of languages that can be $k$-list identified in the limit, based on a recursive version of Angluin's characterization (for language identification with a list of size $1$). This further leads to a conceptually appealing characterization: A language collection can be $k$-list identified in the limit if and only if the collection can be decomposed into $k$ collections of languages, each of which can be identified in the limit (with a list of size $1$). We also use our characterization to establish rates for list identification in the statistical setting where the input is drawn as an i.i.d. stream from a distribution supported on some language in the collection. Our results show that if a collection is $k$-list identifiable in the limit, then the collection can be $k$-list identified at an exponential rate, and this is best possible. On the other hand, if a collection is not $k$-list identifiable in the limit, then it cannot be $k$-list identified at any rate that goes to zero.

  PublisherOA PDFDOI

• 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 instance and underlying metric space, chooses a candidate whose cost differs from the true optimum by only a small factor (known as the distortion)?

  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

• AF: Small: Approximation Techniques for Combinatorial Optimization

  NSF · $131k · 2015–2016

• CAREER: Approximation Algorithms - New Directions and Techniques

  NSF · $400k · 2003–2009

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)