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..
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
Authors: Vincent Cohen-Addad, Tommaso D’Orsi, Aida Mousavifar
ICML 2024 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the fine-grained complexity of the problem and present the first near-linear time algorithm that achieves similar performances to that of (Makarychev et al., 2012). Our algorithm runs in time O(|V (G)|1+o(1) + |E(G)|1+o(1)) and finds a balanced cut of value O(α) . |
| Researcher Affiliation | Collaboration | 1Google Research 2BIDSA, Bocconi. |
| Pseudocode | Yes | Algorithm 1 Fast and robust algorithm for balanced cut; Algorithm 2 Matrix multiplicative weights algorithm for SDPs; Algorithm 3 Approximate matrix multiplicative weights algorithm for SDPs; Algorithm 4 Fast heavy vertex removal procedure; Algorithm 5 Subroutine of fast heavy vertex removal procedure. |
| Open Source Code | No | The paper does not provide any statements about releasing source code, nor does it include links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not involve training models on publicly available datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental validation with dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithmic complexity rather than empirical performance on specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and describes algorithms mathematically. It does not mention any specific software packages or libraries with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe an experimental setup with hyperparameters or training configurations for empirical evaluation. |