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. https://resolver.caltech.edu/CaltechAUTHORS:20190528-132709883

PDF - Submitted Version
See Usage Policy.
582kB

Use this Persistent URL to link to this item: https://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:

URL	URL Type	Description
https://doi.org/10.1016/j.tcs.2019.04.004	DOI	Article
https://arxiv.org/abs/1808.08905	arXiv	Discussion 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

Funders:

Funding Agency	Grant Number
Office of Naval Research (ONR)	N00014-17-12146
Institute for Quantum Information and Matter (IQIM)	UNSPECIFIED
NSF	PHY-1733907
Air Force Office of Scientific Research (AFOSR)	F4FGA06060J007
Air Force Office of Scientific Research (AFOSR)	F4FGA06088J001
Simons Foundation	UNSPECIFIED

DOI:

10.1016/j.tcs.2019.04.004

Record Number:

CaltechAUTHORS:20190528-132709883

Persistent URL:

https://resolver.caltech.edu/CaltechAUTHORS:20190528-132709883

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, 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:

16 Nov 2021 17:16

Repository Staff Only: item control page