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].
Near-Optimal Correlation Clustering with Privacy
Authors: Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub M. Tarnawski
NeurIPS 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we introduce a simple and computationally efficient algorithm for the correlation clustering problem with provable privacy guarantees. Our additive error is stronger than those obtained in prior work and is optimal up to polylogarithmic factors for fixed privacy parameters... Our algorithm is given in Section 3 as Algorithm 1. Its privacy is proved in Section 4 (Theorem 4.5), and Section 5 is devoted to the approximation guarantees (Theorem 5.5)... We remark that the other known works on differentially private correlation clustering also do not provide experimental evaluations... |
| Researcher Affiliation | Collaboration | Vincent Cohen-Addad Google Research EMAIL Chenglin Fan Pennsylvania State University EMAIL Silvio Lattanzi Google Research EMAIL Slobodan Mitrovic UC Davis EMAIL Ashkan Norouzi-Fard Google Research EMAIL Nikos Parotsidis Google Research EMAIL Jakub Tarnawski Microsoft Research EMAIL |
| Pseudocode | Yes | In this section we formally define our algorithm, whose pseudo code is available in Algorithm 1 together with Definition 3.1. ... Algorithm 1: Private correlation clustering using noised agreement |
| Open Source Code | No | In the 'If you ran experiments...' section of the checklist, the response for 'Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)?' is [N/A], indicating no source code is provided. |
| Open Datasets | No | The paper is theoretical and does not present experimental results based on datasets. The checklist under 'If you ran experiments...' explicitly states 'N/A' for data and reproduction, and the Future Work section discusses the challenges of applying the algorithm to 'real-world datasets' and mentions that 'other known works... also do not provide experimental evaluations'. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments that would involve dataset splits. The checklist under 'If you ran experiments...' explicitly states 'N/A' for training details. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. The 'If you ran experiments...' section of the checklist explicitly states 'N/A' for compute resources. |
| Software Dependencies | No | The paper is theoretical and does not describe specific software dependencies with version numbers needed to replicate experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and theoretical guarantees, rather than practical implementation details. No experimental setup details, such as hyperparameters or training settings, are provided in the text. |