Career: random sampling of structures on graphs

This Project Grant award for $313,927.00 was provided by the National Science Foundation (NSF) under the Computer and Information Science and Engineering (CISE) program (CFDA 47.070). The award will fund research at Claremont McKenna College to study fundamental mathematics and algorithms for random sampling of structures on graphs, which has applications in areas like quantifying and detecting gerrymandering. The research aims to improve the speed and reliability of random sampling methods, including exploring techniques from statistical physics. Part of the award will also support a summer program for students to learn about math, computer science, and data science motivated by problems related to democracy. The research period runs from Oct 1, 2025 to Sep 30, 2030.

Abstract

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.- subawards are not planned for this award.