Hongyang Liu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Hongyang Liu has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Yitong Yin
Nanjing University, Nanjing, China
2 shared publications - David G. Harris
University of Maryland, College Park, MD, USA
1 shared publication - Vladimir Kolmogorov
Institute of Science and Technology Austria, Klosterneuburg, Austria
1 shared publication - Yiyao Zhang
School of Computer Science, State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University, Nanjing, China
1 shared publication
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 550-559
Near-Optimal Parallel Approximate Counting via Sampling
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 550-559
Open AccessNear-Optimal Parallel Approximate Counting via Sampling
- Open Access
- 25 January 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (1) , 1-33
Parallelize Single-Site Dynamics up to Dobrushin Criterion
Single-site dynamics are canonical Markov chain based algorithms for sampling from high-dimensional distributions, such as the Gibbs distributions of graphical models. We introduce a simple and generic parallel algorithm that faithfully simulates single-site dynamics. Under a much relaxed, asymptotic variant of the ℓ p -Dobrushin’s condition—where the Dobrushin’s influence matrix has a bounded ℓ p -induced operator norm for an arbitrary p ∈ [1, ∞]—our algorithm simulates N steps of single-site updates within a parallel depth of O ( N / n +log n ) on Õ( m ) processors, where n is the number of sites and m is the size of the graphical model. For Boolean-valued random variables, if the ℓ p -Dobrushin’s condition holds—specifically, if the ℓ p -induced operator norm of the Dobrushin’s influence matrix is less than 1—the parallel depth can be further reduced to O (log N + log n ), achieving an exponential speedup. These results suggest that single-site dynamics with near-linear mixing times can be parallelized into RNC sampling algorithms, independent of the maximum degree of the underlying graphical model, as long as the Dobrushin influence matrix maintains a bounded operator norm. We show the effectiveness of this approach with RNC samplers for the hardcore and Ising models within their uniqueness regimes, as well as an RNC SAT sampler for satisfying solutions of conjunctive normal form formulas in a local lemma regime. Furthermore, by employing non-adaptive simulated annealing, these RNC samplers can be transformed into RNC algorithms for approximate counting.
- 25 January 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (1) , 1-33
Open AccessParallelize Single-Site Dynamics up to Dobrushin Criterion
Single-site dynamics are canonical Markov chain based algorithms for sampling from high-dimensional distributions, such as the Gibbs distributions of graphical models. We introduce a simple and generic parallel algorithm that faithfully simulates single-site dynamics. Under a much relaxed, asymptotic variant of the ℓ p -Dobrushin’s condition—where the Dobrushin’s influence matrix has a bounded ℓ p -induced operator norm for an arbitrary p ∈ [1, ∞]—our algorithm simulates N steps of single-site updates within a parallel depth of O ( N / n +log n ) on Õ( m ) processors, where n is the number of sites and m is the size of the graphical model. For Boolean-valued random variables, if the ℓ p -Dobrushin’s condition holds—specifically, if the ℓ p -induced operator norm of the Dobrushin’s influence matrix is less than 1—the parallel depth can be further reduced to O (log N + log n ), achieving an exponential speedup. These results suggest that single-site dynamics with near-linear mixing times can be parallelized into RNC sampling algorithms, independent of the maximum degree of the underlying graphical model, as long as the Dobrushin influence matrix maintains a bounded operator norm. We show the effectiveness of this approach with RNC samplers for the hardcore and Ising models within their uniqueness regimes, as well as an RNC SAT sampler for satisfying solutions of conjunctive normal form formulas in a local lemma regime. Furthermore, by employing non-adaptive simulated annealing, these RNC samplers can be transformed into RNC algorithms for approximate counting.