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].
Maximum Selection and Sorting with Adversarial Comparators
Authors: Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha Suresh
JMLR 2018 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study maximum selection and sorting of n numbers using imperfect pairwise comparators. ... Against the non-adaptive adversary, we derive a maximum-selection algorithm that uses at most 2n comparisons in expectation and a sorting algorithm that uses at most 2n ln n comparisons in expectation. ... Our study is motivated by a density-estimation problem. ... Using our algorithm, the runtime reduces to Θ(n log n). We propose algorithms with linear query complexity and approximation guarantees. Lemma 4 shows that compl gives a 2-approximation against both adversaries. |
| Researcher Affiliation | Collaboration | Jayadev Acharya EMAIL School of ECE Cornell University Ithaca, NY 14853, USA, Moein Falahatgar EMAIL ECE Department UC San Diego La Jolla, CA 92093, USA, Ashkan Jafarpour EMAIL Google Sunnyvale, CA 94089, USA, Alon Orlitsky EMAIL ECE and CSE Departments UC San Diego La Jolla, CA 92093, USA, Ananda Theertha Suresh EMAIL Google Research New York, NY 10011, USA |
| Pseudocode | Yes | Algorithm compl Complete tournament, Algorithm seq Sequential selection, Algorithm ko-sub Subroutine for ko-mod and comb, Algorithm ko-mod Modified knock-out algorithm, Algorithm qs-sub Subroutine for q-select and comb, Algorithm q-select Quick-select, Algorithm comb Knock-out and quick-select combination, Algorithm scheffe-test Scheffe test for two distributions, Algorithm compl-sort Complete tournament |
| Open Source Code | No | The paper does not provide concrete access to source code. No repository link or explicit code release statement is found. |
| Open Datasets | No | The paper discusses theoretical problems involving 'samples from an unknown distribution p0' or 'a known set Pδ of n distributions' in the context of density estimation, but it does not specify or provide access information for any particular dataset used in empirical evaluations. |
| Dataset Splits | No | The paper does not describe any experiments that would require dataset splits (training, validation, test). It focuses on theoretical analysis and algorithm design without empirical evaluation on specific datasets. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments requiring specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper focuses on theoretical algorithms and their analysis. It does not mention any specific software dependencies or versions used for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and proofs. It does not include an experimental section or details on hyperparameters, training configurations, or system-level settings. |