11 citations · 27 across the 14 of their papers we have counts for
19 papers
Wealth Dynamics Over Generations: Analysis and Interventions
Krishna Acharya, Eshwar Ram Arunachaleswaran, Sampath Kannan +2
We present a stylized model with feedback loops for the evolution of a population's wealth over generations. Individuals have both talent and wealth: talent is a random variable di…
Reconstructing Ultrametric Trees from Noisy Experiments
Eshwar Ram Arunachaleswaran, Anindya De, Sampath Kannan
The problem of reconstructing evolutionary trees or phylogenies is of great interest in computational biology. A popular model for this problem assumes that we are given the set of…
Best vs. All: Equity and Accuracy of Standardized Test Score Reporting
Sampath Kannan, Mingzi Niu, Aaron Roth +1
We study a game theoretic model of standardized testing for college admissions. Students are of two types; High and Low. There is a college that would like to admit the High type s…
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
Yu Chen, Sampath Kannan, Sanjeev Khanna
We consider the problem of designing sublinear time algorithms for estimating the cost of a minimum metric traveling salesman (TSP) tour. Specifically, given access to a $n \times…
Near-Perfect Recovery in the One-Dimensional Latent Space Model
Yu Chen, Sampath Kannan, Sanjeev Khanna
Suppose a graph is stochastically created by uniformly sampling vertices along a line segment and connecting each pair of vertices with a probability that is a known decreasing…
Fair Prediction with Endogenous Behavior
Christopher Jung, Sampath Kannan, Changhwa Lee +3
There is increasing regulatory interest in whether machine learning algorithms deployed in consequential domains (e.g. in criminal justice) treat different demographic groups "fair…
Pipeline Interventions
Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth +1
We introduce the \emph{pipeline intervention} problem, defined by a layered directed acyclic graph and a set of stochastic matrices governing transitions between successive layers.…
A Center in Your Neighborhood: Fairness in Facility Location
Christopher Jung, Sampath Kannan, Neil Lutz
When selecting locations for a set of facilities, standard clustering algorithms may place unfair burden on some individuals and neighborhoods. We formulate a fairness concept that…
Quantifying the Burden of Exploration and the Unfairness of Free Riding
Christopher Jung, Sampath Kannan, Neil Lutz
We consider the multi-armed bandit setting with a twist. Rather than having just one decision maker deciding which arm to pull in each round, we have different decision makers…
Downstream Effects of Affirmative Action
Sampath Kannan, Aaron Roth, Juba Ziani
We study a two-stage model, in which students are 1) admitted to college on the basis of an entrance exam which is a noisy signal about their qualifications (type), and then 2) tho…
Fairness Incentives for Myopic Agents
Sampath Kannan, Michael Kearns, Jamie Morgenstern +4
We consider settings in which we wish to incentivize myopic agents (such as Airbnb landlords, who may emphasize short-term profits and property safety) to treat arriving clients fa…
Privacy-Preserving Data Analysis for the Federal Statistical Agencies
John Abowd, Lorenzo Alvisi, Cynthia Dwork +3
Government statistical agencies collect enormously valuable data on the nation's population and business activities. Wide access to these data enables evidence-based policy making,…
Linear Sketching over
Sampath Kannan, Elchanan Mossel, Grigory Yaroslavtsev
We initiate a systematic study of linear sketching over . For a given Boolean function a randomized -sketch is a distribu…
Private Pareto Optimal Exchange
Sampath Kannan, Jamie Morgenstern, Ryan Rogers +1
We consider the problem of implementing an individually rational, asymptotically Pareto optimal allocation in a barter-exchange economy where agents are endowed with goods and have…
Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)
Sampath Kannan, Jamie Morgenstern, Aaron Roth +1
We present a mechanism for computing asymptotically stable school optimal matchings, while guaranteeing that it is an asymptotic dominant strategy for every student to report their…
Near-Linear Query Complexity for Graph Inference
Sampath Kannan, Claire Mathieu, Hang Zhou
How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? Let be an unweighted, connected graph of bounded degree. The…
Optimal Provision-After-Wait in Healthcare
Mark Braverman, Jing Chen, Sampath Kannan
We investigate computational and mechanism design aspects of scarce resource allocation, where the primary rationing mechanism is through waiting times. Specifically we consider al…
The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal
Zhiyi Huang, Sampath Kannan
In this paper we show that for any mechanism design problem with the objective of maximizing social welfare, the exponential mechanism can be implemented as a truthful mechanism wh…
Variance on the Leaves of a Tree Markov Random Field: Detecting Character Dependencies in Phylogenies
Deeparnab Chakrabarty, Sampath Kannan, Kevin Tian
Stochastic models of evolution (Markov random fields on trivalent trees) generally assume that different characters (different runs of the stochastic process) are independent and i…