This National Science Foundation project grant of $487,371 will support research at the University of California, Santa Barbara from May 2022 through April 2025 under the Computer and Information Science and Engineering program.
The grant will fund the development of new techniques for proving optimal convergence rates of Markov chain Monte Carlo algorithms. Specifically, the researchers will strengthen and extend the technique of spectral independence to establish optimal mixing time bounds for Markov chains sampling from distributions on combinatorial sets. This has applications in Bayesian inference, statistical physics, and theoretical computer science. The project will also formalize connections between the computational complexity of approximate counting problems on graphs and phase transitions in statistical physics on trees. Additionally, an interdisciplinary summer school will train graduate students on recent developments in the research area.