3 papers
cs.CC2022
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…
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.IT2018
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…