BARC Talk by Jiaheng Wang

Towards derandomising Markov chain Monte Carlo

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 loga rithmic 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.

Joint work with Weiming Feng (Edinburgh→Berkeley→ETH Zürich), Heng Guo (Edinburgh), Chunyang Wang (Nanjing) and Yitong Yin (Nanjing).

Biography:
Jiaheng Wang is currently a third-year PhD student at the University of Edinburgh, supervised by Heng Guo. His research is mainly focused on algorithms and complexity of counting problems.