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].
Sublinear Space Private Algorithms Under the Sliding Window Model
Authors: Jalaj Upadhyay
ICML 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution in this paper is a differentially private algorithm for finding heavy hitters in the sliding window model with space complexity o(w), and an additive error guarantee of o(w) over the entire window. We show that it is not the case and we need at least O(log w) space even if we want a constant multiplicative approximation. We do this by reducing the problem of computing private heavy hitter in the sliding window model to one-way communication complexity of augmented index problem (AIND). |
| Researcher Affiliation | Academia | 1Department of Computer Science, Johns Hopkins University, Baltimore, MD 21218. Correspondence to: Jalaj Upadhyay <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 PRIVATE-L1-HEAVY ((xt)t 1; w; "; (γ, , β) and Algorithm 2 PRIVATE-HEAVY ((xt)t 1; w; "; γ; β; k) |
| Open Source Code | No | The paper does not contain any statement about making code available or provide a link to a code repository for its methodology. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and analysis; it does not describe experiments involving dataset training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for validation. |
| Hardware Specification | No | The paper is purely theoretical and does not report on any experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is purely theoretical and does not report on any experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is purely theoretical and does not report on any experiments or provide details on experimental setup such as hyperparameters or training settings. |