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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
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. |