New frontiers in approximate counting
STOC 2020 workshop
General Information
- Date : June 22nd
- Time : CDT1 12:00 – 15:00
- Organizers : Heng Guo (Edinburgh) and Jingcheng Liu (Caltech)
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 …
Schedule
- CDT 12:00 – 12:05 First half remarks (New techniques for sampling)
- CDT 12:05 – 12:45 Kuikui Liu (UW): New tools for analysis of Markov chains via high-dimensional expansion [slides]
- CDT 12:45 – 13:25 Yitong Yin (NJU): Dynamic and distributed algorithms for sampling from Gibbs distributions [slides]
- CDT 13:25 – 13:35 Water break
- CDT 13:35 – 13:40 Second half remarks (Surprising algorithms)
- CDT 13:40 – 14:20 Will Perkins (UIC):
Counting and sampling algorithms at low temperature [slides]
Many approaches to approximate counting and sampling for spin models on graphs rely on parameters belonging to a regime of weak interaction or “high temperature” in the language of statistical physics. Stronger interactions present a barrier to these methods since phase transitions in the underlying model on various classes of graphs induce long-range correlations. How can we count and sample efficiently in the presence of long-range correlations? I will describe one approach using polymer models and the cluster expansion and then survey some of the challenges in the area.
- CDT 14:20 – 15:00 Ankur Moitra (MIT): A Happy Marriage Between Approximate Counting and the Algorithmic Local Lemma [slides]
The local time in Chicago, Central Daylight Saving Time, UTC -5↩︎