# On the Complexity of Sampling Redistricting Plans

arXiv: https://arxiv.org/abs/2206.04883 · HTML: https://mlsanity.com/paper/2206.04883/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2022.

## Built on by (most cited first, 1 of 1)

- [The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions](https://mlsanity.com/paper/2510.17714/) (2025)

## Abstract (arXiv)

A crucial task in the political redistricting problem is to sample redistricting plans i.e. a partitioning of the graph of census blocks into districts. We show that Recombination [DeFord-Duchin-Solomon'21]-a popular Markov chain to sample redistricting plans-is exponentially slow mixing on simple subgraph of mathbbZ2. We show an alternative way to sample balance, compact and contiguous redistricting plans using a "relaxed" version of ReCom and rejection sampling.