Profile Reconstruction from Private Sketches
Authors: Hao Wu, Rasmus Pagh
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show how to speed up their LP-based technique from polynomial time to O(d + n log n), where d = |D|, and analyze the achievable error in the ℓ1, ℓ2 and ℓ∞ norms. In all cases the dependency of the error on d is O(1/d) we give an informationtheoretic lower bound showing that this dependence on d is asymptotically optimal among all private, updatable sketches for the profile reconstruction problem with a high-probability error guarantee. |
| Researcher Affiliation | Academia | 1Department of Computer Science, University of Copenhagen, Denmark. |
| Pseudocode | Yes | Algorithm 1 Private Profile Generator A( r), Algorithm 2 Fast Inversion Afst-inv, Algorithm 3 Rounding Arnd, Algorithm 4 Protocol P, Algorithm 5 Iterated Adjustment |
| Open Source Code | No | The paper does not contain any statements about providing open-source code for the described methodology, nor does it include links to a code repository. |
| Open Datasets | No | The paper is theoretical and defines terms like 'multiset of n items from D' and 'finite domain D' but does not specify any particular dataset or provide concrete access information for a publicly available dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe any experimental validation process, nor does it specify any dataset splits (training, validation, test). |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware specifications (e.g., CPU, GPU models, memory) used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not provide specific software dependencies with version numbers for experimental setup. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, including hyperparameters or system-level training settings. |