Publications (8)
Efficient Multiparty Interactive Coding for Insertions, Deletions and Substitutions
Ran Gelles, Yael T. Kalai, Govind Ramnarayan
In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop…
Equalizing Financial Impact in Supervised Learning
Govind Ramnarayan
Notions of "fair classification" that have arisen in computer science generally revolve around equalizing certain statistics across protected groups. This approach has been critici…
From Soft Classifiers to Hard Decisions: How fair can we be?
Ran Canetti, Aloni Cohen, Nishanth Dikkala +3
A popular methodology for building binary decision-making classifiers in the presence of imperfect information is to first construct a non-binary "scoring" classifier that is calib…
A Geometric Model of Opinion Polarization
Jan HÄ zÅa, Yan Jin, Elchanan Mossel +1
We introduce a simple, geometric model of opinion polarization. It is a model of political persuasion, as well as marketing and advertising, utilizing social values. It focuses on…
Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't
Yan Jin, Elchanan Mossel, Govind Ramnarayan
We consider a variation of the problem of corruption detection on networks posed by Alon, Mossel, and Pemantle '15. In this model, each vertex of a graph can be either truthful or…
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian
Dana Moshkovitz, Govind Ramnarayan, Henry Yuen
In this work we show a barrier towards proving a randomness-efficient parallel repetition, a promising avenue for achieving many tight inapproximability results. Feige and Kilian (…
How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories
Younhun Kim, Frederic Koehler, Ankur Moitra +2
Reconstruction of population histories is a central problem in population genetics. Existing coalescent-based methods, like the seminal work of Li and Durbin (Nature, 2011), attemp…
Efficient Reconstruction of Stochastic Pedigrees
Younhun Kim, Elchanan Mossel, Govind Ramnarayan +1
We introduce a new algorithm called {\sc Rec-Gen} for reconstructing the genealogy or \textit{pedigree} of an extant population purely from its genetic data. We justify our approac…