Complexity of the Stable Invitations Problem
Authors: Hooyeon Lee, Vassilevska Williams
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we study the complexity of SIP on a finer scale, through the lense of parameterized complexity. For the two solution concepts and the special cases where the number of friends and/or enemies is bounded above by a constant, we show that the problems belong to different complexity classes when parameterized by the size of solutions. |
| Researcher Affiliation | Academia | Hooyeon Lee, Virginia Vassilevska Williams Computer Science Department Stanford University {haden.lee,virgi}@cs.stanford.edu |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention providing open-source code for the described methodologies. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or evaluation, therefore no information about publicly available datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation, training, or testing. |
| Hardware Specification | No | The paper is theoretical and does not involve experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not involve implemented systems requiring software dependencies. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup or hyperparameters. |