1 citations · 1 across the 13 of their papers we have counts for
6 papers · 1 filter
Stable Voting Rules on the Edge of Optimal Metric Distortion
Ziyi Cai, Moses Charikar, Jabari Hastings +3
We prove the existence of a randomized voting rule with metric distortion at most , within of the lower bound of . Our rule comes from a generalization of…
Pessimal Elections for Approximately Dominating Sets
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
Condorcet's paradox is a foundational result in social choice theory, showing that no matter which candidate wins an election, a majority of voters may prefer some losing candidate…
Language Identification with Succinct Machine-Independent Traces
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
Motivated by the power of large language models, there has been renewed interest in the Gold-Angluin model of language identification in the limit, with an eye toward variants of t…
Globally Consistent Coloring Schemes for Language Identification
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
We study how little extra information is needed to make adversarial language learning possible. In Gold's model of language identification in the limit, a learner is given an enume…
An Exposition of Five Candidates Suffice for a Majority
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
We give a brief exposition of a result of Song, Nguyen, and Lin (2026) that every election (with ranked preferences) has a Condorcet winning set of at most five candidates.
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
Moses Charikar, Chirag Pabbaraju, Ambuj Tewari
Curvature adaptivity is a classical theme in online optimization: for convex Lipschitz losses, adaptive methods interpolate between the optimal regret for general con…