23 citations · 101 across the 39 of their papers we have counts for
7 papers · 1 filter
Sampling Arborescences in Parallel
Nima Anari, Nathan Hu, Amin Saberi +1
We study the problem of sampling a uniformly random directed rooted spanning tree, also known as an arborescence, from a possibly weighted directed graph. Classically, this problem…
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…
Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases
Nima Anari, Michał Dereziński
We define a notion of isotropy for discrete set distributions. If is a distribution over subsets of a ground set , we say that is in isotropic position if $P[e \in…
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,…
An Extension of Plücker Relations with Applications to Subdeterminant Maximization
Nima Anari, Thuy-Duong Vuong
Given a matrix and , we study the problem of finding the submatrix of with the maximum determinant in absolute value. This problem is motivated by the…
Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests
Nima Anari, Kuikui Liu, Shayan Oveis Gharan +2
We prove tight mixing time bounds for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomia…