From the 1 of 8 linked papers with an AI index.
8 papers
Parallel Sampling from the Ising -Spin Model
Nima Anari, Aniket Das, Alireza Haqi
The paper introduces two parallel algorithms for sampling from the high‑temperature Ising mixed p‑spin Gibbs measure, achieving polylogarithmic parallel time and significantly redu…
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-pla…
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…
Fast Spanning Tree Sampling in Broadcast Congested Clique
Nima Anari, Alireza Haqi
We present the first polylogarithmic-round algorithm for sampling a random spanning tree in the (Broadcast) Congested Clique model. For any constant , our algorithm outputs…