Publications

(2025). Approximately counting knapsack solutions in subquadratic time. In SODA 2025.

(2025). Optimal mixing for randomly sampling edge colorings on trees down to the max degree. In SODA 2025.

PDF

(2024). Rapid mixing of the flip chain over non-crossing spanning trees.

PDF

(2024). Approximate counting for spin systems in sub-quadratic time. In ICALP 2024.

PDF Jiaheng's slides

(2023). Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields. Information and Computation (IANDC) 294: 105066 (2023).

PDF

(2023). A simple polynomial-time approximation algorithm for the total variation distance between two product distributions. TheoretiCS, Volume 2 (2023), Article 8, 1-7 (conference version in SOSA 2023).

PDF Talk@Simons Poster@Zinal Slides@Zinal Slides@PKU Jiaheng's slides

(2022). Optimal mixing for two-state anti-ferromagnetic spin systems. In FOCS 2022.

PDF Slides@FOCS

(2022). Improved bounds for randomly colouring simple hypergraphs. In RANDOM 2022.

PDF Jiaheng's slides

(2022). Rapid mixing from spectral independence beyond the Boolean domain. ACM Transactions on Algorithms (TALG) 18(3): 28:1-28:32 (conference version in SODA 2021).

PDF Slides@SODA

(2022). Perfect sampling from spatial mixing. Random Structures & Algorithms (RSA) 61(4): 678-709.

PDF Slides@E-PIC

(2021). Fast sampling and counting k-SAT solutions in the local lemma regime. Journal of the ACM (JACM) 68 (6), 1-42 (Conference version in STOC 2020).

PDF Talk@STOC Talk@IJTCS Slides@STOC Slides@ICT_CAS Heng's slides Heng's talk

(2021). Dynamic sampling from graphical models. SIAM Journal on Computing (SICOMP), 50(2), 350–381. (Confernece version in STOC 2019).

PDF Poster@STOC Slides@STOC Yitong's slides Yitong's talk

(2021). Distributed Metropolis sampler with optimal parallelism. In SODA 2021.

PDF Slides@SODA Yitong's slides

(2021). Dynamic inference in probabilistic graphical models. In ITCS 2021.

PDF Kun's talk

(2020). What can be sampled locally?. Distributed Computing (DC) 33, 227–253 (conference version in PODC 2017).

PDF Yitong's slides

(2018). On local distributed sampling and counting. In PODC 2018.

PDF Yitong's slides