Weiming Feng 0001

SODA Conference 2025 Conference Paper

Approximately Counting Knapsack Solutions in Subquadratic Time

• Weiming Feng 0001
• Ce Jin 0001

FOCS Conference 2025 Conference Paper

Deterministic Counting from Coupling Independence

• Xiaoyu Chen
• Weiming Feng 0001
• Heng Guo 0001
• Xinyuan Zhang
• Zongrui Zou

We show that spin systems with bounded degrees and coupling independence admit fully polynomial time approximation schemes (FPTAS). We design a new recursive deterministic counting algorithm to achieve this. As applications, we give the first FPTASes for q-colourings on graphs of bounded maximum degree $\Delta \geq 3$, when $q \geq\left(11 / 6-\varepsilon_{0}\right) \Delta$ for some small $\varepsilon_{0} \approx 10^{-5}$, or when $\Delta \geq 125$ and $q \geq 1. 809 \Delta$, and on graphs with sufficiently large (but constant) girth, when $q \geq \Delta+3$. These bounds match the current best randomised approximate counting algorithms by Chen, Delcourt, Moitra, Perarnau, and Postle (2019), Carlson and Vigoda (2024), and Chen, Liu, Mani, and Moitra (2023), respectively.

FOCS Conference 2025 Conference Paper

Faster Mixing of the Jerrum-Sinclair Chain

• Xiaoyu Chen
• Weiming Feng 0001
• Zhe Ju
• Tianshun Miao
• Yitong Yin
• Xinyuan Zhang

We show that the Jerrum-Sinclair Markov chain on matchings mixes in time $\widetilde{O}\left(\Delta^{2} m\right)$ on any graph with n vertices, m edges, and maximum degree $\Delta$, for any constant edge weight $\lambda\gt 0$. For general graphs with arbitrary, potentially unbounded $\Delta$, this provides the first improvement over the classic $\widetilde{O}\left(n^{2} m\right)$ mixing time bound of Jerrum and Sinclair (1989) and Sinclair (1992). To achieve this, we develop a general framework for analyzing mixing times, combining ideas from the classic canonical path method with the “local-to-global” approaches recently developed in high-dimensional expanders, introducing key innovations to both techniques.

SODA Conference 2025 Conference Paper

Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree

• Charlie Carlson
• Xiaoyu Chen
• Weiming Feng 0001
• Eric Vigoda

SODA Conference 2024 Conference Paper

On Deterministically Approximating Total Variation Distance

• Weiming Feng 0001
• Liqiang Liu
• Tianren Liu

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

Optimal mixing for two-state anti-ferromagnetic spin systems

• Xiaoyu Chen
• Weiming Feng 0001
• Yitong Yin
• Xinyuan Zhang

We prove an optimal $\Omega(n^{-1})$ lower bound for modified $\log$-Sobolev (MLS) constant of the Glauber dynamics for anti-ferromagnetic two-spin systems with n vertices in the tree uniqueness regime. Specifically, this optimal MLS bound holds for the following classes of two-spin systems in the tree uniqueness regime: (1) all strictly anti-ferromagnetic two-spin systems (where both edge parameters $\beta, \gamma\leq$ 1), which cover the hardcore models and the anti-ferromagnetic Ising models; (2) general antiferromagnetic two-spin systems on regular graphs. Consequently, an optimal $O(n\log n)$ mixing time holds for these anti-ferromagnetic two-spin systems when the uniqueness condition is satisfied. These MLS and mixing time bounds hold for any bounded or unbounded maximum degree, and the constant factors in the bounds depend only on the gap to the uniqueness threshold. We prove this by showing a boosting theorem for MLS constant for distributions satisfying certain spectral independence and marginal stability properties.

SODA Conference 2021 Conference Paper

Distributed Metropolis Sampler with Optimal Parallelism

• Weiming Feng 0001
• Thomas P. Hayes
• Yitong Yin

SODA Conference 2021 Conference Paper

Rapid Mixing from Spectral Independence beyond the Boolean Domain

• Weiming Feng 0001
• Heng Guo 0001
• Yitong Yin
• Chihao Zhang 0001

We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [2]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper q -colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided q ≥ ( α ∗ + δ )Δ where α ∗ ≈ 1. 763 is the unique solution to α ∗ = exp (1/ α ∗) and δ > 0 is any constant. This is the first efficient algorithm for sampling proper q -colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [19].

FOCS Conference 2021 Conference Paper

Rapid mixing of Glauber dynamics via spectral independence for all degrees

• Xiaoyu Chen
• Weiming Feng 0001
• Yitong Yin
• Xinyuan Zhang

We prove an optimal $\Omega(n^{-1})$ lower bound on the spectral gap of Glauber dynamics for anti-ferromagnetic two-spin systems with $n$ vertices in the tree uniqueness regime. This spectral gap holds for any, including unbounded, maximum degree Δ. Consequently, we have the following mixing time bounds for the models satisfying the uniqueness condition with a slack $\delta\in(0, 1)$: • $C(\delta)n^{2}\log n$ mixing time for the hardcore model with fugacity $\leq(1-\delta)\lambda_{c}(\Delta)=(1-\delta)\frac{(\Delta-1)^{\Delta-1}}{(\Delta-2)^{\Delta}}$; • $C(\delta)n^{2}$ mixing time for the Ising model with edge activity $\beta\in[\frac{\Delta-2+\delta}{\Delta-\delta}, \frac{\Delta-\delta}{\Delta-2+\delta}]$; where the maximum degree Δ may depend on the number of vertices n, and C(δ) depends only on δ. Our proof is built upon the recently developed connections between the Glauber dynamics for spin systems and the high-dimensional expander walks. In particular, we prove a stronger notion of spectral independence, called the complete spectral independence, and use a novel Markov chain called the field dynamics to connect this stronger spectral independence to the rapid mixing of Glauber dynamics for all degrees.

STOC Conference 2021 Conference Paper

Sampling constraint satisfaction solutions in the local lemma regime

• Weiming Feng 0001
• Kun He 0011
• Yitong Yin

We give a Markov chain based algorithm for sampling almost uniform solutions of constraint satisfaction problems (CSPs). Assuming a canonical setting for the Lovász local lemma, where each constraint is violated by a small number of forbidden local configurations, our sampling algorithm is accurate in a local lemma regime, and the running time is a fixed polynomial whose dependency on n is close to linear, where n is the number of variables. Our main approach is a new technique called state compression , which generalizes the “mark/unmark” paradigm of Moitra, and can give fast local-lemma-based sampling algorithms. As concrete applications of our technique, we give the current best almost-uniform samplers for hypergraph colorings and for CNF solutions.

STOC Conference 2020 Conference Paper

Fast sampling and counting k-SAT solutions in the local lemma regime

• Weiming Feng 0001
• Heng Guo 0001
• Yitong Yin
• Chihao Zhang 0001

STOC Conference 2019 Conference Paper

Dynamic sampling from graphical models

• Weiming Feng 0001
• Nisheeth K. Vishnoi
• Yitong Yin

In this paper, we study the problem of sampling from a graphical model when the model itself is changing dynamically with time. This problem derives its interest from a variety of inference, learning, and sampling settings in machine learning, computer vision, statistical physics, and theoretical computer science. While the problem of sampling from a static graphical model has received considerable attention, theoretical works for its dynamic variants have been largely lacking. The main contribution of this paper is an algorithm that can sample dynamically from a broad class of graphical models over discrete random variables. Our algorithm is parallel and Las Vegas: it knows when to stop and it outputs samples from the exact distribution. We also provide sufficient conditions under which this algorithm runs in time proportional to the size of the update, on general graphical models as well as well-studied specific spin systems. In particular we obtain, for the Ising model (ferromagnetic or anti-ferromagnetic) and for the hardcore model the first dynamic sampling algorithms that can handle both edge and vertex updates (addition, deletion, change of functions), both efficient within regimes that are close to the respective uniqueness regimes, beyond which, even for the static and approximate sampling, no local algorithms were known or the problem itself is intractable. Our dynamic sampling algorithm relies on a local resampling algorithm and a new ``equilibrium'' property that is shown to be satisfied by our algorithm at each step, and enables us to prove its correctness. This equilibrium property is robust enough to guarantee the correctness of our algorithm, helps us improve bounds on fast convergence on specific models, and should be of independent interest.