Generalized Kings and Single-Elimination Winners in Random Tournaments
Authors: Pasin Manurangsi, Warut Suksompong
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we provide an almost complete characterization of the probability threshold such that all, a large number, or a small number of alternatives are k-kings with high probability in two random models. We show that, perhaps surprisingly, all changes in the threshold occur in the range of constant k, with the biggest change being between k = 2 and k = 3. In addition, we establish an asymptotically tight bound on the probability threshold for which all alternatives are likely able to win a single-elimination tournament under some bracket. |
| Researcher Affiliation | Collaboration | Pasin Manurangsi1 and Warut Suksompong2 1Google Research, USA 2School of Computing, National University of Singapore, Singapore pasin@google.com, warut@comp.nus.edu.sg |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code, nor does it explicitly state that code for its methodology is open source. |
| Open Datasets | No | The paper is theoretical and does not utilize or refer to publicly available datasets for training, validation, or testing. |
| Dataset Splits | No | The paper is theoretical and does not provide specific dataset split information for reproduction. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not provide specific experimental setup details such as hyperparameters or training configurations. |