Abstract
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.
Weiming Feng
Research Associate
I am a research associate (postdoc) in the School of Informatics, University of Edinburgh. My research interest lies in theoretical computer science. Currently, I focus on sampling and counting algorithms.
Heng Guo
Reader
I am a reader in algorithms and complexity in the School of informatics, University of Edinburgh. My research focuses on algorithms from a complexity perspective.
Chunyang Wang
Ph.D Student
I am currently a fourth-year Ph.D student in the Theory Group in the Department of Computer Science and Technology at Nanjing University. My research interest lies in a broad aspect of computer science. Currently, I am focusing on algorithms for counting and sampling.
Jiaheng Wang
Ph.D Student
I am a Ph.D student at the School of Informatics, University of Edinburgh. My research interest lies in several topics in theoretical computer science.
Yitong Yin
Professor
I am a professor in the Theory Group in the Department of Computer Science and Technology at Nanjing University. I am interested in Theoretical Computer Science.