Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP
Authors: Jiehua Chen, Robert Ganian, Thekla Hamm
IJCAI 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate the following many-to-one stable matching problem with diversity constraints (SMTI-DIVERSE)... SMTI-DIVERSE is known to be NP-hard. However, as opposed to the NP-membership claims in the literature [Aziz et al., 2019; Huang, 2010], we prove that it is beyond NP: it is complete for the complexity class ΣP 2. In addition, we provide a comprehensive analysis of the problem s complexity from the viewpoint of natural restrictions to inputs and obtain new algorithms for the problem. |
| Researcher Affiliation | Academia | Jiehua Chen , Robert Ganian and Thekla Hamm TU Wien, Vienna, Austria EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. It provides proof sketches and theoretical analysis. |
| Open Source Code | No | The paper does not include any statement about releasing source code or provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on complexity analysis and algorithm design without empirical evaluation on specific datasets. Therefore, it does not mention dataset availability. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits. Thus, no training/validation/test splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments that would require specific software dependencies with version numbers. No such details are provided. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity analysis and algorithm design. It does not describe an experimental setup with hyperparameters or system-level training settings. |