Moses Charikar
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Moses Charikar has a total of 61 co-authors. Here are the top co-authors by number of shared publications:
- Prasanna Ramakrishnan
Stanford University Stanford University
6 shared publications - Aaron Sidford
Stanford University
3 shared publications - Chirag Pabbaraju
Stanford University
3 shared publications - Kangning Wang
Rutgers University, Piscataway, USA
3 shared publications - Gregory Valiant
Stanford University Stanford University Stanford University
2 shared publications - Kirankumar Shiragur
National University of Singapore Broad Institute of MIT Harvard
2 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1881-1891
A (4+ϵ)-Approximation for Euclidean k-Means via Non-monotone Dual-Fitting
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1881-1891
Open AccessA (4+ϵ)-Approximation for Euclidean k-Means via Non-monotone Dual-Fitting
- Open Access
A Characterization of List Language Identification in the Limit
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.Open AccessA Characterization of List Language Identification in the Limit
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. - Open Access
Pareto-optimal Non-uniform Language Generation
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.Open AccessPareto-optimal Non-uniform Language Generation
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. - Open Access
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 790-818
Metric Distortion for Tournament Voting and Beyond
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 790-818
Open AccessMetric Distortion for Tournament Voting and Beyond
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1590-1601
Six Candidates Suffice to Win a Voter Majority
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1590-1601
Open AccessSix Candidates Suffice to Win a Voter Majority
- Open Access
Metric Distortion for Tournament Voting and Beyond
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.Open AccessMetric Distortion for Tournament Voting and Beyond
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. - Open Access
- 8 November 2024
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 71 (6) , 1-33
Breaking the Metric Voting Distortion Barrier
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, 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 )? A long line of work culminated in finding optimal deterministic voting rules with metric distortion 3. However, for randomized voting rules, there is still a significant gap in our understanding: even though the best lower bound is substantially lower at 2.112, the best upper bound is still 3, which is attained even by simple rules such as Random Dictatorship. Finding a randomized rule that guarantees distortion 3 - ɛ for some constant ɛ has been a major challenge in computational social choice, as prevalent approaches to designing voting rules are known to be insufficient. In particular, such a voting rule must use information beyond aggregate comparisons between pairs of candidates, and cannot only assign positive probability to candidates that are voters’ top choices. In this work, we give a rule that guarantees distortion less than 2.753. To do so, we study a handful of voting rules that are new to the problem. One is Maximal Lotteries , a rule based on the Nash equilibrium of a natural zero-sum game that dates back to the 1960s. The others are novel rules that can be thought of as hybrids of Random Dictatorship and the Copeland rule. None of these rules can beat distortion 3 alone; however, a careful randomization between Maximal Lotteries and any of the novel rules can.
- 8 November 2024
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 71 (6) , 1-33
Open AccessBreaking the Metric Voting Distortion Barrier
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, 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 )? A long line of work culminated in finding optimal deterministic voting rules with metric distortion 3. However, for randomized voting rules, there is still a significant gap in our understanding: even though the best lower bound is substantially lower at 2.112, the best upper bound is still 3, which is attained even by simple rules such as Random Dictatorship. Finding a randomized rule that guarantees distortion 3 - ɛ for some constant ɛ has been a major challenge in computational social choice, as prevalent approaches to designing voting rules are known to be insufficient. In particular, such a voting rule must use information beyond aggregate comparisons between pairs of candidates, and cannot only assign positive probability to candidates that are voters’ top choices. In this work, we give a rule that guarantees distortion less than 2.753. To do so, we study a handful of voting rules that are new to the problem. One is Maximal Lotteries , a rule based on the Nash equilibrium of a natural zero-sum game that dates back to the 1960s. The others are novel rules that can be thought of as hybrids of Random Dictatorship and the Copeland rule. None of these rules can beat distortion 3 alone; however, a careful randomization between Maximal Lotteries and any of the novel rules can.
- Open Access
Dynamic Data Layout Optimization with Worst-case Guarantees
Many data analytics systems store and process large datasets in partitions containing millions of rows. By mapping rows to partitions in an optimized way, it is possible to improve query performance by skipping over large numbers of irrelevant partitions during query processing. This mapping is referred to as a data layout. Recent works have shown that customizing the data layout to the anticipated query workload greatly improves query performance, but the performance benefits may disappear if the workload changes. Reorganizing data layouts to accommodate workload drift can resolve this issue, but reorganization costs could exceed query savings if not done carefully. In this paper, we present an algorithmic framework OReO that makes online reorganization decisions to balance the benefits of improved query performance with the costs of reorganization. Our framework extends results from Metrical Task Systems to provide a tight bound on the worst-case performance guarantee for online reorganization, without prior knowledge of the query workload. Through evaluation on real-world datasets and query workloads, our experiments demonstrate that online reorganization with OReO can lead to an up to 32% improvement in combined query and reorganization time compared to using a single, optimized data layout for the entire workload.
Open AccessDynamic Data Layout Optimization with Worst-case Guarantees
Many data analytics systems store and process large datasets in partitions containing millions of rows. By mapping rows to partitions in an optimized way, it is possible to improve query performance by skipping over large numbers of irrelevant partitions during query processing. This mapping is referred to as a data layout. Recent works have shown that customizing the data layout to the anticipated query workload greatly improves query performance, but the performance benefits may disappear if the workload changes. Reorganizing data layouts to accommodate workload drift can resolve this issue, but reorganization costs could exceed query savings if not done carefully. In this paper, we present an algorithmic framework OReO that makes online reorganization decisions to balance the benefits of improved query performance with the costs of reorganization. Our framework extends results from Metrical Task Systems to provide a tight bound on the worst-case performance guarantee for online reorganization, without prior knowledge of the query workload. Through evaluation on real-world datasets and query workloads, our experiments demonstrate that online reorganization with OReO can lead to an up to 32% improvement in combined query and reorganization time compared to using a single, optimized data layout for the entire workload.
- Open Access
Recovery Guarantees for Quadratic Tensors with Sparse Observations
We consider the tensor completion problem of predicting the missing entries of a tensor. The commonly used CP model has a triple product form, but an alternate family of quadratic models, which are the sum of pairwise products instead of a triple product, have emerged from applications such as recommendation systems. Non-convex methods are the method of choice for learning quadratic models, and this work examines their sample complexity and error guarantee. Our main result is that with the number of samples being only linear in the dimension, all local minima of the mean squared error objective are global minima and recover the original tensor. We substantiate our theoretical results with experiments on synthetic and real-world data, showing that quadratic models have better performance than CP models where there are a limited amount of observations available.
Open AccessRecovery Guarantees for Quadratic Tensors with Sparse Observations
We consider the tensor completion problem of predicting the missing entries of a tensor. The commonly used CP model has a triple product form, but an alternate family of quadratic models, which are the sum of pairwise products instead of a triple product, have emerged from applications such as recommendation systems. Non-convex methods are the method of choice for learning quadratic models, and this work examines their sample complexity and error guarantee. Our main result is that with the number of samples being only linear in the dimension, all local minima of the mean squared error objective are global minima and recover the original tensor. We substantiate our theoretical results with experiments on synthetic and real-world data, showing that quadratic models have better performance than CP models where there are a limited amount of observations available.
- Open Access
The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction
We study the effect of Johnson-Lindenstrauss transforms in various projective clustering problems, generalizing recent results which only applied to center-based clustering [MMR19]. We ask the general question: for a Euclidean optimization problem and an accuracy parameter $\epsilon \in (0, 1)$, what is the smallest target dimension $t \in \mathbb{N}$ such that a Johnson-Lindenstrauss transform $\Pi \colon \mathbb{R}^d \to \mathbb{R}^t$ preserves the cost of the optimal solution up to a $(1+\epsilon)$-factor. We give a new technique which uses coreset constructions to analyze the effect of the Johnson-Lindenstrauss transform. Our technique, in addition applying to center-based clustering, improves on (or is the first to address) other Euclidean optimization problems, including: $\bullet$ For $(k,z)$-subspace approximation: we show that $t = \tilde{O}(zk^2 / \epsilon^3)$ suffices, whereas the prior best bound, of $O(k/\epsilon^2)$, only applied to the case $z = 2$ [CEMMP15]. $\bullet$ For $(k,z)$-flat approximation: we show $t = \tilde{O}(zk^2/\epsilon^3)$ suffices, completely removing the dependence on $n$ from the prior bound $\tilde{O}(zk^2 \log n/\epsilon^3)$ of [KR15]. $\bullet$ For $(k,z)$-line approximation: we show $t = O((k \log \log n + z + \log(1/\epsilon)) / \epsilon^3)$ suffices, and ours is the first to give any dimension reduction result.Open AccessThe Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction
We study the effect of Johnson-Lindenstrauss transforms in various projective clustering problems, generalizing recent results which only applied to center-based clustering [MMR19]. We ask the general question: for a Euclidean optimization problem and an accuracy parameter $\epsilon \in (0, 1)$, what is the smallest target dimension $t \in \mathbb{N}$ such that a Johnson-Lindenstrauss transform $\Pi \colon \mathbb{R}^d \to \mathbb{R}^t$ preserves the cost of the optimal solution up to a $(1+\epsilon)$-factor. We give a new technique which uses coreset constructions to analyze the effect of the Johnson-Lindenstrauss transform. Our technique, in addition applying to center-based clustering, improves on (or is the first to address) other Euclidean optimization problems, including: $\bullet$ For $(k,z)$-subspace approximation: we show that $t = \tilde{O}(zk^2 / \epsilon^3)$ suffices, whereas the prior best bound, of $O(k/\epsilon^2)$, only applied to the case $z = 2$ [CEMMP15]. $\bullet$ For $(k,z)$-flat approximation: we show $t = \tilde{O}(zk^2/\epsilon^3)$ suffices, completely removing the dependence on $n$ from the prior bound $\tilde{O}(zk^2 \log n/\epsilon^3)$ of [KR15]. $\bullet$ For $(k,z)$-line approximation: we show $t = O((k \log \log n + z + \log(1/\epsilon)) / \epsilon^3)$ suffices, and ours is the first to give any dimension reduction result.