From the 2 of 12 linked papers with an AI index.
12 papers
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
The paper shows that language identification in the limit can be achieved using compact, machine‑independent computational traces that use only a small alphabet derived directly fr…
Globally Consistent Coloring Schemes for Language Identification
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
The paper shows that a single terminal bit attached to each example string is sufficient to identify any countable collection of infinite languages in Gold's language identificatio…
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…
Approximately Dominating Sets in Elections
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
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…