Events
Colloquium
Random Redistricting via Random Walks
 |
Speaker: Jamie Tucker-Foltz Assistant Professor of Operations and Computer Science Wednesday, February 11, 2026 11:30AM - 1:00PM Lunch at 11:30am in 1307
Talk 12:00-1:00pm in 1327 Location: Yale Institute for Foundations of Data Science & Webcast, 219 Prospect Street, 13th Floor, New Haven, CT 06511 and via Webcast: https://yale.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=b6625cbd-34c8-4d20-985a-b3d80149eb4b |
Abstract: A widely-used method for assessing fairness in political redistricting is to generate a massive ensemble of “random” redistricting maps to develop a statistical baseline, i.e., a null model for what an unbiased map-maker would produce. State-of-the-art algorithms accomplish this task by sampling random spanning trees on the underlying graph of geographical subunits and removing edges. The resulting sub-trees then define a partition of the graph into districts. A bottleneck of this process is generating random spanning trees. In this talk, I will describe this redistricting problem and show how we can leverage additional information about the embedding of the graph in the plane to circumvent this step, rapidly generating a graph partition from the same distribution without drawing a complete spanning tree. This technique gives a theoretical asymptotic speedup, with preliminary results suggesting it is faster in practice as well. Based on joint work with Sarah Cannon, Christopher Pankow, and Wesley Pegden. See:
https://arxiv.org/abs/2508.11130 (working paper on new algorithm)
https://arxiv.org/abs/2310.15152 (older STOC paper it builds on)
Speaker Bio: Jamie Tucker-Foltz is an Assistant Professor in Operations at SOM, with a secondary appointment in Computer Science.
He is broadly interested in the design of fair political and economic institutions. He works on a range of topics in fair division, social choice, and algorithmic game theory, drawing on mathematical tools and methodologies from operations research, economics, and theoretical computer science. He is especially interested in algorithms for fair redistricting and gerrymandering detection.
Jamie completed his PhD in computer science at Harvard University, advised by Ariel Procaccia. He also holds a master’s degree in computer science from the University of Cambridge and a bachelor’s degree in computer science and mathematics from Amherst College.
Add To: Google Calendar | Outlook | iCal File
- Colloquium
Submit an Event
Interested in creating your own event, or have an event to share? Please fill the form if you’d like to send us an event you’d like to have added to the calendar.