11 citations · 27 across the 14 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…
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…
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…