Manipulating Districts to Win Elections: Fine-Grained Complexity
Authors: Eduard Eiben, Fedor Fomin, Fahad Panolan, Kirill Simonov1902-1909
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate the rigorous study of the gerrymandering problem from the perspectives of parameterized and fine-grained complexity and provide asymptotically matching lower and upper bounds on its computational complexity. We prove that the problem is W[1]-hard parameterized by k + n and that it does not admit an f(n, k) mo(k) algorithm for any function f of k and n only, unless the Exponential Time Hypothesis (ETH) fails. Our lower bounds hold already for 2 parties. On the other hand, we give an algorithm that solves the problem for a constant number of parties in time (m + n)O(k). |
| Researcher Affiliation | Academia | 1Department of Computer Science, Royal Holloway, University of London, UK 2Department of Informatics, University of Bergen, Norway 3Department of Computer Science and Engineering, IIT Hyderabad, India |
| Pseudocode | No | The paper describes algorithms and proofs but does not include any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is open-source or publicly available. |
| Open Datasets | No | This is a theoretical paper that does not use datasets for training or empirical evaluation. |
| Dataset Splits | No | This is a theoretical paper that does not involve dataset validation splits. |
| Hardware Specification | No | This is a theoretical paper, and thus no hardware specifications for running experiments are provided. |
| Software Dependencies | No | This is a theoretical paper and does not specify any software dependencies with version numbers needed to replicate empirical results. |
| Experiment Setup | No | This is a theoretical paper, and therefore, no experimental setup details like hyperparameters or training configurations are relevant or provided. |