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

One research associate position available for a fixed term of 24 months. Apply here. The closing date is Dec 19th, 2023.

One research associate position is available. Fixed term of 24 months. Apply here. The closing date is February 28th, 2023.

Up to two research associates positions are now available. The positions are fixed term of 24 months. Apply here. The closing date is February 18th, 2022.

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 (under LFCS) as the potential supervisor. It would also help to contact me in advance.

Team members

Postdocs

Ph.D. students

Visitors

Research output