CAREER: Random Sampling of Structures on Graphs

When analyzing large systems that have an enormous number of possibilities, studying collections of randomly selected pieces can provide an effective way to understand likely properties or behaviors of the entire system. Random sampling can be applied to polling, estimating quantities in physical systems, detecting gerrymandering, and more. However, it is challenging to do random sampling in a way that is both fast and accurate. This project will study the fundamental mathematics behind methods for random sampling, including introducing new sampling methods, developing new tools to analyze existing sampling methods, and finding problems amenable to the new approaches the investigator develops. One goal is to improve methods used to quantify and detect gerrymandering, making those methods both faster and more reliable. Part of the award will support a summer program where students learn about math, computer science, and data science motivated by problems related to democracy. This project considers random sampling of structures on graphs, such as spin configurations on the vertices of a graph or partitions of a graph into connected pieces. In one direction, the investigator will consider Pirogov-Sinai theory (PST), an approach from statistical physics that could help advance the state-of-the-art in sampling/counting algorithms for spin systems and more. Specific questions include adapting PST from infinite to finite settings; using PST and the additional probabilistic information it conveys to develop new Markov chain sampling algorithms; and exploring other statistical physics ideas that can lead to algorithmic breakthroughs. In another direction, tree-based methods have emerged as a promising way to sample connected graph partitions, but existing algorithms remain insufficient for fast, provably accurate sampling in general settings. Work on this project will address this gap, building on insights from a recent breakthrough result. This is closely tied to broader questions about the combinatorial and probabilistic structure of random trees and random walks, Markov chain mixing under non-local constraints, and duality in non-planar graphs. As political districting plans can be viewed as connected balanced partitions of population-weighted graphs (and random sampling algorithms are widely used to detect gerrymandering, understand possible plans, and advocate for voting rights, including in court), advances in efficiently generating these structures have broad implications for political science and important societal impact. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.