Theory seminar: We are excited to host Jamie Tucker-Foltz from Harvard University for this week's theory seminar! Please join us on November 18th at 10 am in Siebel 3401. Please see their abstract below:
Abstract: When judging the fairness of a political redistricting map, it is useful to be able to generate a large ensemble of "random" alternative maps. Formally, this is a graph partitioning problem. The objective is to output random partitions of the vertex set into k equal-sized pieces inducing connected subgraphs. Numerous algorithms have been developed to sample either exactly or approximately from the so-called "spanning tree distribution," where each partition is weighted by the product of the numbers of spanning trees in each part. However, none of these algorithms had been shown to run in polynomial time, even on very tame families of graphs. In 2022, Charikar, Liu, Liu, and Vuong proposed a simple algorithm, and conjectured that it runs in polynomial time on grid graphs for constant k. We prove this conjecture, and extend to a wide class of "grid-like" planar graphs encapsulating the kinds of graphs typically encountered in real geographical data.
Based on joint work with Sarah Cannon and Wesley Pegden.