8 papers
Sampling Line-Graph Colorings with Constant Extra Colors
Alireza Haqi
Let be the line graph of a finite simple graph, with vertices and maximum degree . We prove that single-site Glauber dynamics for uniform proper -colorings mixes…
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 . Aires and Kahn…
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 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…
Improving Order with Queues
Andreas Karrenbauer, Kurt Mehlhorn, Pranabendu Misra +4
Given a sequence of numbers and parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that queues suffice to sort…