Chunyang Wang 0003

STOC Conference 2025 Conference Paper

Counting Random k-SAT near the Satisfiability Threshold

• Zongchen Chen
• Aditya Lonkar
• Chunyang Wang 0003
• Kuan Yang 0001
• Yitong Yin

STOC Conference 2025 Conference Paper

Phase Transitions via Complex Extensions of Markov Chains

• Jingcheng Liu 0001
• Chunyang Wang 0003
• Yitong Yin
• Yixiao Yu

We study algebraic properties of partition functions, particularly the location of zeros, through the lens of rapidly mixing Markov chains. The classical Lee-Yang program initiated the study of phase transitions via locating complex zeros of partition functions. Markov chains, besides serving as algorithms, have also been used to model physical processes tending to equilibrium. In many scenarios, rapid mixing of Markov chains coincides with the absence of phase transitions (complex zeros). Our motivating example is the independence polynomial on k -uniform hypergraphs, where the best-known zero-free regime has been significantly lagging behind the regime where we have rapidly mixing Markov chains for the underlying hypergraph independent sets. Specifically, the Glauber dynamics is known to mix rapidly on independent sets in a k -uniform hypergraph of maximum degree Δ provided that Δ ≲ 2 k /2 . On the other hand, the best-known zero-freeness around the point 1 of the independence polynomial on k -uniform hypergraphs requires Δ ≤ 5, the same bound as on a graph. By introducing a complex extension of Markov chains, we lift an existing percolation argument to the complex plane, and show that if Δ ≲ 2 k /2 , the Markov chain converges in a complex neighborhood, and the independence polynomial itself does not vanish in the same neighborhood. In the same regime, our result also implies central limit theorems for the size of a uniformly random independent set, and deterministic approximation algorithms for the number of hypergraph independent sets of size k ≤ α n for some constant α.

FOCS Conference 2024 Conference Paper

A Sampling Lovász Local Lemma for Large Domain Sizes

• Chunyang Wang 0003
• Yitong Yin

We present polynomial-time algorithms for approximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regime: \begin{equation*} pD^{2+o_{q}(1)}\lesssim 1. \end{equation*} When the domain size $q$ of each variable becomes sufficiently large, this almost matches the known lower bound $pD^{2}\lesssim 1$ for approximate counting and sampling solutions to atomic CSPs [1], [2], thus establishing an almost tight sampling Lovasz local lemma for large domain sizes.

SODA Conference 2023 Conference Paper

Deterministic counting Lovász local lemma beyond linear programming

• Kun He 0011
• Chunyang Wang 0003
• Yitong Yin

FOCS Conference 2023 Conference Paper

Towards derandomising Markov chain Monte Carlo

• Weiming Feng 0001
• Heng Guo 0001
• Chunyang Wang 0003
• Jiaheng Wang 0002
• Yitong Yin

We present a new framework to derandomise certain Markov chain Monte Carlo (MCMC) algorithms. As in MCMC, we first reduce counting problems to sampling from a sequence of marginal distributions. For the latter task, we introduce a method called coupling towards the past that can, in logarithmic time, evaluate one or a constant number of variables from a stationary Markov chain state. Since there are at most logarithmic random choices, this leads to very simple derandomisation. We provide two applications of this framework, namely efficient deterministic approximate counting algorithms for hypergraph independent sets and hypergraph colourings, under local lemma type conditions matching, up to lower order factors, their state-of-the-art randomised counterparts.

FOCS Conference 2022 Conference Paper

Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time

• Kun He 0011
• Chunyang Wang 0003
• Yitong Yin

We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Ihe expected running time of our algorithm is near-linear in n and a fixed polynomial in $\Delta$, where n is the number of variables and $\Delta$ is the max degree of constraints. Previously, up to similar conditions, sampling algorithms with running time polynomial in both n and $\Delta$, only existed for the almost atomic case, where each constraint is violated by a small number of forbidden local configurations.