Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests

DOI10.1145/3406325.3451091arXiv2004.07220OpenAlexW3168179120MaRDI QIDQ6087012

Shayan Oveis Gharan, Thuy Duong Vuong, Nima Anari, Kuikui Liu, Cynthia Vinzant

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.07220

zbMATH Keywords

random walkdiscrete optimizationexchange propertycounting and samplingnear-linear time algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Extended L-ensembles: a new representation for determinantal point processes ⋮ Modified log-Sobolev inequalities for strong-Rayleigh measures ⋮ On the convexity of general inverse \(\sigma_k\) equations ⋮ Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid