4 citations · 7 across the 10 of their papers we have counts for
16 papers
Pareto Inefficiency of EFX
Sepideh Mahabadi, Prasanna Ramakrishnan, Jakub Tarnawski
We consider the problem of allocating indivisible goods to agents with additive valuations, under two classic notions of fairness and efficiency: envy-freeness up to any good (EFX)…
Optimal Shallow Circuits for Majority
Victor Lecomte, Prasanna Ramakrishnan
Four decades on, Håstad's classical lower bound for depth- circuits computing Parity remains the best known circuit lower bound for any expl…
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…
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.
Distortion of Metric Voting with Bounded Randomness
Ziyi Cai, D. D. Gao, Prasanna Ramakrishnan +1
We study the design of voting rules in the metric distortion framework. It is known that any deterministic rule suffers distortion of at least , and that randomized rules can ac…
Fair metric distortion for matching with preferences
Jabari Hastings, Prasanna Ramakrishnan
We consider the matching problem in the metric distortion framework. There are agents and items occupying points in a shared metric space, and the goal is to design a match…
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…
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…
Breaking the Metric Voting Distortion Barrier
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang +1
We consider the following well-studied problem of metric distortion in social choice. Suppose we have an election with voters and candidates located in a shared metric spac…
Distortion in metric matching with ordinal preferences
Nima Anari, Moses Charikar, Prasanna Ramakrishnan
Suppose that we have agents and items which lie in a shared metric space. We would like to match the agents to items such that the total distance from agents to their match…
The composition complexity of majority
Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan
We study the complexity of computing majority as a composition of local functions: \[ \text{Maj}_n = h(g_1,\ldots,g_m), \] where each is an arbitrary…
Metric Distortion Bounds for Randomized Social Choice
Moses Charikar, Prasanna Ramakrishnan
Consider the following social choice problem. Suppose we have a set of voters and candidates that lie in a metric space. The goal is to design a mechanism to choose a candi…
Tradeoffs for small-depth Frege proofs
Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan
We study the complexity of small-depth Frege proofs and give the first tradeoffs between the size of each line and the number of lines. Existing lower bounds apply to the overall p…
On taking advantage of multiple requests in error correcting codes
Prasanna Ramakrishnan, Mary Wootters
In most notions of locality in error correcting codes -- notably locally recoverable codes (LRCs) and locally decodable codes (LDCs) -- a decoder seeks to learn a single symbol of…