New frontiers in approximate counting

STOC 2020 workshop

General Information

Approximate counting and sampling is a classical topic in theoretical computer science. Despite the great success of the Markov chain Monte Carlo method in the late 80s / early 90s, a number of fundamental problems remain open. In recent years, a few exciting techniques have emerged and the old challenges start to crumble. These new techniques range from novel ways to analyze / apply Markov chains, to brand new sampling and counting algorithms exploiting insights from combinatorics, probability theory, statistical physics, and optimization. This workshop is dedicated to these new frontiers.

How to join watch?

Please register at STOC 2020 and use the zoom link.

The recording is available here.

Unfortunately Yitong’s talk (from about 0:44:20 to 1:26:20) was not recorded correctly. The slides froze at the presentation mode. Please watch here for a re-synced version. Alternatively, as the slides are available below, you can also manually turn the slides while listening to the audio …


  1. The local time in Chicago, Central Daylight Saving Time, UTC -5↩︎