From the 1 of 6 linked papers with an AI index.
6 papers
On the Gap of Finite Posets
Alireza Haqi
Let be a finite nonempty poset with elements, let be a uniformly random order-preserving bijection, and put . Define $\operat…
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…
On Thin Perfect Matchings up to Polylogarithmic Factors
Alireza Haqi, Shayan Oveis Gharan
We resolve the thin matching problem proposed by Anari, Charikar and Ramakrishnan [ACR23] up to polylogarithmic factors. Given a fractional perfect matching , we say a perfect m…
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)\)…
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…
Parallel Sampling via Autospeculation
Nima Anari, Carlo Baronio, CJ Chen +4
We present parallel algorithms to accelerate sampling via counting in two settings: any-order autoregressive models and denoising diffusion models. An any-order autoregressive mode…