ERC starting grant

New Approaches to Counting and Sampling (NACS)

General information

Project description

The project focuses on a class of computational tasks, technically known as the counting and sampling problems. Typically a complicated distribution is involved, and the task is to estimate the probability of certain events, or draw samples from the said distribution. The goal of the project is to understand the computational complexity of such tasks.

Markov chain Monte Carlo algorithms have been designed and applied for counting and sampling long before the computational complexity theory, and they are among the oldest randomised algorithms. There had been dramatic progress in the rigorous analysis of Markov chains in the early 90s, which has lead to many landmark results. Nevertheless, after about 30 years’ development, the complexity of many fundamental problems remains open. In the last few years, a number of exciting approaches have emerged, resulting from new perspectives and surprising connections. Roughly speaking, there are two themes of the new techniques, namely utilising the Lovász local lemma or the geometry of polynomials. As a consequence of the new techniques, a lot of old challenges has started to crumble. It is now the right time to revisit some of the oldest problems in counting complexity.

Open position

Up to two research associates positions are now available. The positions are fixed term of 24 months. Apply here. The closing date is January 6th, 2021.

Fundings for Ph.D. students are also available. Please adhere to the standard application procedure to the School of Informatics, as described here, and indicate Heng Guo as the potential supervisor.

Team members


Ph.D. students


To be updated

Research output