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..
Median Selection with Noisy and Structural Information
Authors: Chenglin Fan, Mingyu Kang
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We complement our analysis with extensive experiments on synthetic data. 5 Experiments We empirically evaluate our algorithms in two settings: (1) the classical total order case, where a weak comparison oracle is available, and (2) the partially ordered case, where the input is a synthetic DAG and only standard comparisons are used. |
| Researcher Affiliation | Academia | Chenglin Fan Seoul National University Seoul 08826, South Korea EMAIL Mingyu Kang Seoul National University Seoul 08826, South Korea EMAIL |
| Pseudocode | Yes | The algorithm is detailed in Algorithm 1. [...] The general procedure for partitioning using a DAG structure is outlined in Algorithm 2, while the randomized median selection using a DAG is presented in Algorithm 3, and the deterministic median selection using a DAG is detailed in Algorithm 4 in the Appendix. |
| Open Source Code | Yes | All source code used for these experiments is provided in the supplementary material as a ZIP archive. |
| Open Datasets | No | All experiments use synthetic data: we vary the weak oracle accuracy in the total-order case and control the DAG width in the partial-order case. [...] Our experiments are conducted on synthetic datasets to enable controlled evaluations where parameters such as noise levels and DAG width can be systematically varied, allowing us to validate our theoretical findings. |
| Dataset Splits | No | We begin by evaluating our modified Lazy Select algorithm on arrays of size n = 105 and n = 106, each a random permutation of {0, . . . , n 1}. [...] We next evaluate the impact of structural information by comparing both the randomized (Algorithm 3) and deterministic (Algorithm 4) median selection algorithms, with and without access to DAG structure, on synthetic partial orders over n = 104 elements. |
| Hardware Specification | Yes | Experiments were conducted on a Mac Book Air (M1, 2020) with 8 GB RAM. |
| Software Dependencies | Yes | All code was compiled under the C++17 standard with the -O3 optimization flag. |
| Experiment Setup | Yes | We begin by evaluating our modified Lazy Select algorithm on arrays of size n = 105 and n = 106, each a random permutation of {0, . . . , n 1}. We report the exact median success rate and the normalized number of strong oracle calls per element across weak oracle accuracies 1 p {0.51, 0.75, 0.9, 1.0} and weak comparison budgets c d, where d = log n and c {1, 2, 4, 8, 16}. Each configuration is repeated 100 times, and we report average results. [...] We next evaluate the impact of structural information by comparing both the randomized (Algorithm 3) and deterministic (Algorithm 4) median selection algorithms, with and without access to DAG structure, on synthetic partial orders over n = 104 elements. DAGs are generated by randomly adding edges while preserving acyclicity, and we control the width w (size of the largest antichain) by varying edge density in steps of 500. Results are averaged over 10 trials per width. |