14 citations · 32 across the 32 of their papers we have counts for
5 papers · 1 filter
Instance Based Approximations to Profile Maximum Likelihood
Nima Anari, Moses Charikar, Kirankumar Shiragur +1
In this paper we provide a new efficient algorithm for approximately computing the profile maximum likelihood (PML) distribution, a prominent quantity in symmetric property estimat…
Distributed Algorithms from Arboreal Ants for the Shortest Path Problem
Shivam Garg, Kirankumar Shiragur, Deborah M. Gordon +1
Colonies of the arboreal turtle ant create networks of trails that link nests and food sources on the graph formed by branches and vines in the canopy of the tropical forest. Ants…
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood
Nima Anari, Moses Charikar, Kirankumar Shiragur +1
In this paper we consider the problem of computing the likelihood of the profile of a discrete distribution, i.e., the probability of observing the multiset of element frequencies,…
On the Competitive Analysis and High Accuracy Optimality of Profile Maximum Likelihood
Yanjun Han, Kirankumar Shiragur
A striking result of [Acharya et al. 2017] showed that to estimate symmetric properties of discrete distributions, plugging in the distribution that maximizes the likelihood of obs…
A General Framework for Symmetric Property Estimation
Moses Charikar, Kirankumar Shiragur, Aaron Sidford
In this paper we provide a general framework for estimating symmetric properties of distributions from i.i.d. samples. For a broad class of symmetric properties we identify the eas…