5 citations · 26 across the 17 of their papers we have counts for
19 papers · 1 filter
Approximating two-terminal network reliability
Weiming Feng, Yucheng Fu, Heng Guo
We present a fully polynomial-time randomised approximation scheme (FPRAS) for the two-terminal reliability problem on general graphs, both directed and undirected. We also show th…
Fast counting and sampling for ferromagnetic two-spin systems
Weiming Feng, Heng Guo, Yichun Yang
We introduce two new models equivalent to ferromagnetic two-spin systems: a weighted subgraph model and a random cluster type model. Using these new connections, we obtain an effic…
An FPRAS for two terminal reliability in directed acyclic graphs
Weiming Feng, Heng Guo
We give a fully polynomial-time randomized approximation scheme (FPRAS) for two terminal reliability in directed acyclic graphs (DAGs). In contrast, we also show the complementing…
Approximate Counting for Spin Systems in Sub-Quadratic Time
Konrad Anand, Weiming Feng, Graham Freifeld +2
We present two randomised approximate counting algorithms with running time for some constant and accuracy : (1) for the h…
Towards derandomising Markov chain Monte Carlo
Weiming Feng, Heng Guo, Chunyang Wang +2
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…
A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
Weiming Feng, Heng Guo, Mark Jerrum +1
We give a simple polynomial-time approximation algorithm for the total variation distance between two product distributions.
Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
Weiming Feng, Heng Guo, Jiaheng Wang
We study the sampling problem for the ferromagnetic Ising model with consistent external fields, and in particular, Swendsen-Wang dynamics on this model. We introduce a new grand m…
Improved bounds for randomly colouring simple hypergraphs
Weiming Feng, Heng Guo, Jiaheng Wang
We study the problem of sampling almost uniform proper -colourings in -uniform simple hypergraphs with maximum degree . For any , if and $q \…
Rapid mixing of Glauber dynamics via spectral independence for all degrees
Xiaoyu Chen, Weiming Feng, Yitong Yin +1
We prove an optimal lower bound on the spectral gap of Glauber dynamics for anti-ferromagnetic two-spin systems with vertices in the tree uniqueness regime. This sp…
Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
Weiming Feng, Kun He, 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, wh…
Rapid mixing from spectral independence beyond the Boolean domain
Weiming Feng, Heng Guo, Yitong Yin +1
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) from the Boolean domain to general discrete domains. This property characterises…
Fast sampling and counting k-SAT solutions in the local lemma regime
Weiming Feng, Heng Guo, Yitong Yin +1
We give new algorithms based on Markov chains to sample and approximately count satisfying assignments to -uniform CNF formulas where each variable appears at most times. Fo…
Perfect sampling from spatial mixing
Weiming Feng, Heng Guo, Yitong Yin
We introduce a new perfect sampling technique that can be applied to general Gibbs distributions and runs in linear time if the correlation decays faster than the neighborhood grow…
Dynamic inference in probabilistic graphical models
Weiming Feng, Kun He, Xiaoming Sun +1
Probabilistic graphical models, such as Markov random fields (MRFs), are useful for describing high-dimensional distributions in terms of local dependence structures. The probabili…
Distributed Metropolis Sampler with Optimal Parallelism
Weiming Feng, Thomas P. Hayes, Yitong Yin
The Metropolis-Hastings algorithm is a fundamental Markov chain Monte Carlo (MCMC) method for sampling and inference. With the advent of Big Data, distributed and parallel variants…
Dynamic Sampling from Graphical Models
Weiming Feng, 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…
On Local Distributed Sampling and Counting
Weiming Feng, Yitong Yin
In classic distributed graph problems, each instance on a graph specifies a space of feasible solutions (e.g. all proper ()-list-colorings of the graph), and the task of distr…
Distributed Symmetry Breaking in Sampling (Optimal Distributed Randomly Coloring with Fewer Colors)
Weiming Feng, Thomas P. Hayes, Yitong Yin
We examine the problem of almost-uniform sampling proper -colorings of a graph whose maximum degree is . A famous result, discovered independently by Jerrum(1995) and Salas a…
What can be sampled locally?
Weiming Feng, Yuxin Sun, Yitong Yin
The local computation of Linial [FOCS'87] and Naor and Stockmeyer [STOC'93] concerns with the question of whether a locally definable distributed computing problem can be solved lo…