4 citations · 28 across the 15 of their papers we have counts for
15 papers
On Interpolating Experts and Multi-Armed Bandits
Houshuang Chen, Yuchen He, Chihao Zhang
Learning with expert advice and multi-armed bandit are two classic online decision problems which differ on how the information is observed in each round of the game. We study a fa…
Sampling Proper Colorings on Line Graphs Using Colors
Yulin Wang, Chihao Zhang, Zihan Zhang
We prove that the single-site Glauber dynamics for sampling proper -colorings mixes in time on line graphs with vertices and maximum degree when $q>(1+o(1…
Improved Algorithms for Bandit with Graph Feedback via Regret Decomposition
Yuchen He, Chihao Zhang
The problem of bandit with graph feedback generalizes both the multi-armed bandit (MAB) problem and the learning with expert advice problem by encoding in a directed graph how the…
A Perfect Sampler for Hypergraph Independent Sets
Guoliang Qiu, Yanheng Wang, Chihao Zhang
The problem of uniformly sampling hypergraph independent sets is revisited. We design an efficient perfect sampler for the problem under a condition similar to that of the asymmetr…
Understanding Bandits with Graph Feedback
Houshuang Chen, Zengfeng Huang, Shuai Li +1
The bandit problem with graph feedback, proposed in [Mannor and Shamir, NeurIPS 2011], is modeled by a directed graph where is the collection of bandit arms, and once…
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…
Zeros of Holant problems: locations and algorithms
Heng Guo, Chao Liao, Pinyan Lu +1
We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised sec…
Counting hypergraph colorings in the local lemma regime
Heng Guo, Chao Liao, Pinyan Lu +1
We give a fully polynomial-time approximation scheme (FPTAS) to count the number of -colorings for -uniform hypergraphs with maximum degree if and $q >357Δ^{\fr…
Canonical Paths for MCMC: from Art to Science
Lingxiao Huang, Pinyan Lu, Chihao Zhang
Markov Chain Monte Carlo (MCMC) method is a widely used algorithm design scheme with many applications. To make efficient use of this method, the key step is to prove that the Mark…
FPTAS for Hardcore and Ising Models on Hypergraphs
Pinyan Lu, Kuan Yang, Chihao Zhang
Hardcore and Ising models are two most important families of two state spin systems in statistic physics. Partition function of spin systems is the center concept in statistic phys…
Spatial mixing and approximate counting for Potts model on graphs with bounded average degree
Yitong Yin, Chihao Zhang
We propose a notion of contraction function for a family of graphs and establish its connection to the strong spatial mixing for spin systems. More specifically, we show that for a…
Sampling colorings almost uniformly in sparse random graphs
Yitong Yin, Chihao Zhang
The problem of sampling proper -colorings from uniform distribution has been extensively studied. Most of existing samplers require for some constants and , w…
FPTAS for Weighted Fibonacci Gates and Its Applications
Pinyan Lu, Menghui Wang, Chihao Zhang
Fibonacci gate problems have severed as computation primitives to solve other problems by holographic algorithm and play an important role in the dichotomy of exact counting for Ho…
Approximate Counting via Correlation Decay on Planar Graphs
Yitong Yin, Chihao Zhang
We show for a broad class of counting problems, correlation decay (strong spatial mixing) implies FPTAS on planar graphs. The framework for the counting problems considered by us i…