23 citations · 34 across the 22 of their papers we have counts for
26 papers · 1 filter
Beyond the Bethe Approximation of the Permanent
Nima Anari
The canonical Bethe approximation gives a deterministic approximation to the permanent of every nonnegative matrix within a factor of . We improve the base of this ex…
Gårding's Theorem for Posynomials
Nima Anari
We extend Gårding's theorem to homogeneous posynomials: if a finite positive sum of monomials with arbitrary nonnegative real exponents is zero-free on a product of right half-plan…
Parallel Sampling from the Ising -Spin Model
Nima Anari, Aniket Das, Alireza Haqi
We study the parallel complexity of sampling from the high-temperature Ising mixed -spin Gibbs measure, a canonical instance of a mean-field spin glass on the hypercube $\{\pm 1…
On Rounding on the Hypersimplex
Nima Anari, Alireza Haqi, Eric Ma
We study correlated rounding on the hypersimplex, the base polytope of the uniform matroid. For each point \(x\) in the hypersimplex, the goal is to sample a \(k\)-subset \(A(x)\)…
Sampling Directed Eulerian Tours in Time
Nima Anari
We give a randomized algorithm that samples a nearly uniform Eulerian tour of a directed Eulerian multigraph with arcs in time. The guarantee is worst-c…
Optimal -Approximation of the Permanent of Positive Semidefinite Matrices
Nima Anari, Farzam Ebrahimnejad
We determine, up to lower-order terms in the exponent, the best possible deterministic polynomial-time approximation ratio for the permanent of a Hermitian positive semidefinite ma…