A Caltech Library Service

Fair redistricting is hard

Kueng, Richard and Mixon, Dustin G. and Villar, Soledad (2019) Fair redistricting is hard. Theoretical Computer Science, 791 . pp. 28-35. ISSN 0304-3975. doi:10.1016/j.tcs.2019.04.004.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Gerrymandering is a long-standing issue within the U.S. political system, and it has received scrutiny recently by the U.S. Supreme Court. In this note, we prove that deciding whether there exists a fair redistricting among legal maps is -hard. To make this precise, we use simplified notions of “legal” and “fair” that account for desirable traits such as geographic compactness of districts and sufficient representation of voters. The proof of our result is inspired by the work of Mahanjan, Minbhorkar and Varadarajan that proves that planar k-means is -hard.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2019 Elsevier B.V. Received 27 August 2018, Revised 6 February 2019, Accepted 15 April 2019, Available online 28 May 2019. The main ideas in this paper were conceived while the authors were attending an Oberwolfach workshop on “Applied Harmonic Analysis and Data Processing” in March 2018. The authors thank Boris Alexeev and Ruth Greenwood for reading a preliminary version of this paper and providing helpful comments. RK was supported in part by Joel A. Tropp under ONR Award No. N00014-17-12146 and also acknowledges funding provided by the Institute of Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). DGM was partially supported by AFOSR F4FGA06060J007 and AFOSR Young Investigator Research Program award F4FGA06088J001. SV was partially supported by the Simons Algorithms and Geometry (A&G) Think Tank. The views expressed in this article are those of the authors and do not reflect the official policy or position of the United States Air Force, Department of Defense, or the U.S. Government.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-17-12146
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)F4FGA06060J007
Air Force Office of Scientific Research (AFOSR)F4FGA06088J001
Simons FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20190528-132709883
Persistent URL:
Official Citation:Richard Kueng, Dustin G. Mixon, Soledad Villar, Fair redistricting is hard, Theoretical Computer Science, Volume 791, 2019, Pages 28-35, ISSN 0304-3975, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:95824
Deposited By: Tony Diaz
Deposited On:28 May 2019 21:25
Last Modified:16 Nov 2021 17:16

Repository Staff Only: item control page