The Complexity of Stable Matchings under Substitutable Preferences
Authors: Yuan Deng, Debmalya Panigrahi, Bo Waggoner
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Note that, although Theorem 2 is technically stated in terms of the number of queries, all computations performed in the algorithm are efficient, hence they run in polynomial time when given an efficient verifier. Therefore, in this paper, we do not distinguish between saying that our algorithm uses a polynomial number of queries and saying that it runs in polynomial time. |
| Researcher Affiliation | Academia | Yuan Deng, Debmalya Panigrahi Department of Computer Science Duke University Durham, NC 27708, USA {ericdy,debmalya}@cs.duke.edu Bo Waggoner Department of Computer Science University of Pennsylvania Philadelphia, PA 19104, USA bwag@seas.upenn.edu |
| Pseudocode | Yes | Algorithm 1: Implementation of the choice function; Algorithm 2: I( ): Find an element v C(D); Algorithm 3: M( ): Find an almost optimal set A of X |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not describe experiments involving datasets. Therefore, no information about public dataset availability is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments or dataset usage. Thus, no training/test/validation split information is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity in terms of queries and polynomial time. It does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers for reproducing empirical work. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments. Therefore, no experimental setup details like hyperparameters or training configurations are provided. |