6 papers
A Characterization of List Language Identification in the Limit
Moses Charikar, Chirag Pabbaraju, Ambuj Tewari
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…
Pareto-optimal Non-uniform Language Generation
Moses Charikar, Chirag Pabbaraju
Kleinberg and Mullainathan (2024) recently proposed an interesting model for language generation in the limit: Given a countable collection of languages, and an adversary enumerati…
Metric Distortion for Tournament Voting and Beyond
Moses Charikar, Prasanna Ramakrishnan, Zihan Tan +1
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 se…
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…
Exploring Facets of Language Generation in the Limit
Moses Charikar, Chirag Pabbaraju
The recent work of Kleinberg & Mullainathan [KM24] provides a concrete model for language generation in the limit: given a sequence of examples from an unknown target language, the…
Six Candidates Suffice to Win a Voter Majority
Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan +2
A cornerstone of social choice theory is Condorcet's paradox which says that in an election where voters rank candidates it is possible that, no matter which candidate is d…