BARC Talk by Weiming Feng

A Markov chain approach to the sampling Lovász local lemma

Abstract:
The constraint satisfaction problem (CSP) is a fundamental object in computer science. The Lovász local lemma is a powerful tool to prove the existence of CSP solutions. We study the sampling Lovász local lemma, which aims to sample a uniform CSP solution in the local lemma regime.  In this talk, I will present an MCMC approach to this problem. Compared to previous results, our sampling algorithm is much faster, and the running time is close to linear.  Our sampling results also imply efficient algorithms for approximately counting the number of CPS solutions. Concrete applications include sampling and counting algorithms for CNF solutions and hypergraph colourings.

About Weiming:
Weiming Feng is a research associate (postdoc) in the School of Informatics, University of Edinburgh. He obtained his Ph.D. degree from Nanjing University in June 2021, where he was advised by Professor Yitong Yin.  His research interest lies in theoretical computer science. Currently, he studies the sampling and approximate counting algorithms.