4 citations · 7 across the 10 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.GT2021
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…
cs.CC2021
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…