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..
Replicable Online pricing
Authors: Kiarash Banihashem, Mohammadhossein Bateni, Hossein Esfandiari, Samira Goudarzi, MohammadTaghi Hajiaghayi
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our first result is an algorithm that replicably outputs a (1/2 ϵ)-competitive threshold with high probability for finite distributions. ... For the ROP problem, we establish that the dependence on the size of X is necessary. ... We next show that, for a suitable choice of the set X, if the distribution X does not contain a heavy element with probability α, then the maximum of M 1/α i.i.d. draws of X is, in expectation, at least Ω(M)E [X] (Lemma 8). ... In this section, we prove Theorem 5 Let D denote the input distribution. We first present our algorithm to solve the problem. We then move on to the analysis of the replicability of the algorithm and its correctness. ... The remainder of the paper is organized as follows. Section 2 discusses the preliminaries of the paper. Section 3 proves the upper bound for ROP. Section 4 proves the lower bound. Finally, Section 5 provides the heavy-hitter algorithm. |
| Researcher Affiliation | Collaboration | Kiarash Banihashem University of Maryland College Park, MD, USA EMAIL Mohammad Hossein Bateni Google Research New York City, New York, USA EMAIL Hossein Esfandiari Google Research London, UK EMAIL Samira Goudarzi University of Maryland College Park, MD, USA EMAIL Mohammad Taghi Hajiaghayi University of Maryland College Park, MD, USA EMAIL |
| Pseudocode | Yes | 5 Replicable Heavy Hitter In this section, we prove Theorem 5 Let D denote the input distribution. We first present our algorithm to solve the problem. We then move on to the analysis of the replicability of the algorithm and its correctness. 5.1 Algorithm We first take a sample S(1) of size n1 = Θ(ν 1 log(ρ 1 + β 1 + ν 1)) from the distribution. Next, we sample a set S(2) with size n2 = Θ(log( n1 min(ρ,β))ν 1 log2(ν 1)/ρ2) Θ(log(ν 1)3 log(ρ 1 + β 1)ρ 2ν 1) samples from the distribution and record, for each element x S(1), the number of times it appears in S(2). Sample ν uniformly at random from the range [3/2ν, 2ν]. Let Y denote the set of all elements in S(1) that appear more than ν n2 times in S(2), where we remove repetitions of an element so that each element appears at most once in Y . If Y is non-empty, we choose an element from it uniformly at random and return as output. |
| Open Source Code | No | The paper is theoretical and does not contain any experiments. (Justification for Question 4 and 5 in NeurIPS Checklist) |
| Open Datasets | No | The paper is theoretical and does not contain any experiments. (Justification for Question 5 in NeurIPS Checklist) |
| Dataset Splits | No | The paper is theoretical and does not contain any experiments. (Justification for Question 4 in NeurIPS Checklist) |
| Hardware Specification | No | The paper is theoretical and does not contain any experiments. (Justification for Question 8 in NeurIPS Checklist) |
| Software Dependencies | No | The paper is theoretical and does not contain any experiments. (Justification for Question 4 in NeurIPS Checklist) |
| Experiment Setup | No | The paper is theoretical and does not contain any experiments. (Justification for Question 6 in NeurIPS Checklist) |