7 papers
Universal Algorithms for Clustering Problems
Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi
This paper presents universal algorithms for clustering problems, including the widely studied -median, -means, and -center objectives. The input is a metric space contain…
Privately Answering Counting Queries with Generalized Gaussian Mechanisms
Arun Ganesh, Jiazheng Zhao
We consider the problem of answering counting (i.e. sensitivity-1) queries about a database with -differential privacy. We give a mechanism such that if the true answer…
Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC
Arun Ganesh, Kunal Talwar
Various differentially private algorithms instantiate the exponential mechanism, and require sampling from the distribution for a suitable function . When the domain…
Near-Linear Time Edit Distance for Indel Channels
Arun Ganesh, Aaron Sy
We consider the following model for sampling pairs of strings: is a uniformly random bitstring of length , and is the bitstring arrived at by applying substitutions,…
Robust Algorithms for TSP and Steiner Tree
Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the e…
Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
Arun Ganesh, Qiuyi Zhang
We consider the phylogenetic tree reconstruction problem with insertions and deletions (indels). Phylogenetic algorithms proceed under a model where sequences evolve down the model…