CaltechAUTHORS
  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 . ISSN 0304-3975. (In Press) http://resolver.caltech.edu/CaltechAUTHORS:20190528-132709883

[img] PDF - Submitted Version
See Usage Policy.

568Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20190528-132709883

Abstract

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
https://doi.org/10.1016/j.tcs.2019.04.004DOIArticle
https://arxiv.org/abs/1808.08905arXivDiscussion 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:IQIM, Institute for Quantum Information and Matter
Funders:
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-17-12146
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSFPHY-1733907
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:http://resolver.caltech.edu/CaltechAUTHORS:20190528-132709883
Official Citation:Richard Kueng, Dustin G. Mixon, Soledad Villar, Fair redistricting is hard, Theoretical Computer Science, 2019, ISSN 0304-3975, https://doi.org/10.1016/j.tcs.2019.04.004. (http://www.sciencedirect.com/science/article/pii/S0304397519302798)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:95824
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:28 May 2019 21:25
Last Modified:28 May 2019 21:25

Repository Staff Only: item control page