Kemeny Consensus Complexity
Authors: Zack Fitzsimmons, Edith Hemaspaandra
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity of consensus-related questions, with a particular focus on Kemeny and its qualitative version Slater. The simplest of these questions is the problem of determining whether a ranking is a consensus, and we show that this problem is co NPcomplete. ... Determining if a given ranking is a Kemeny consensus is co NP-complete. (Section 3) |
| Researcher Affiliation | Academia | 1College of the Holy Cross 2Rochester Institute of Technology zfitzsim@holycross.edu, eh@cs.rit.edu |
| Pseudocode | No | The paper describes methods through prose and mathematical proofs, but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper refers to a 'full version' (Fitzsimmons and Hemaspaandra, 2021) and ar Xiv.org, but does not explicitly state that source code for the described methodology is being released or provide a direct link to a code repository. |
| Open Datasets | No | This is a theoretical paper focused on computational complexity; it does not involve training models on datasets. |
| Dataset Splits | No | This is a theoretical paper focused on computational complexity; it does not describe experimental validation procedures or data splits. |
| Hardware Specification | No | This is a theoretical paper focused on computational complexity; therefore, it does not describe specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper focused on computational complexity; it does not describe specific software dependencies with version numbers for experimental reproduction. |
| Experiment Setup | No | This is a theoretical paper focused on computational complexity; it does not provide details about an experimental setup, hyperparameters, or training settings. |