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].
A Near Linear Query Lower Bound for Submodular Maximization
Authors: Binghui Peng, Aviad Rubinstein
ICML 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We strengthen their lower bound to a nearly tight eā¦(n). This lower bound holds even for estimating the value of the optimal subset. When the objective function is additive, we prove that finding an approximately optimal subset still requires near-linear query complexity, but we can estimate the value of the optimal subset in e O(n/k) queries, and that this is tight up to polylog factors. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Stanford University, United States 2Department of Computer Science, Stanford University, United States. Correspondence to: Binghui Peng <EMAIL>, Aviad Rubinstein <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Reduction: From submodular maximization to distributed set detection Algorithm 2 LINEARSUM(f, k) Algorithm 3 ESTIMATEQUANTILE(g, t) |
| Open Source Code | No | The paper is theoretical, focusing on lower bounds and algorithm design and analysis. There is no mention of releasing code, links to repositories, or supplementary materials containing implementation code for the described methodologies. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and algorithm design. It does not utilize any specific datasets for experimental evaluation, thus no information about public availability of datasets is provided. |
| Dataset Splits | No | The paper does not conduct experiments on datasets; therefore, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and presents mathematical proofs and algorithm designs. It does not describe any experimental setup that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and lower bounds. It does not describe any empirical evaluations that would necessitate listing specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and primarily presents mathematical proofs and algorithm analysis. It does not include any experimental setup details such as hyperparameters or specific training configurations. |