Improved Algorithms for White-Box Adversarial Streams
Authors: Ying Feng, David Woodruff
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study streaming algorithms in the white-box adversarial stream model, where the internal state of the streaming algorithm is revealed to an adversary who adaptively generates the stream updates, but the algorithm obtains fresh randomness unknown to the adversary at each time step. We incorporate cryptographic assumptions to construct robust algorithms against such adversaries. We propose efficient algorithms for sparse recovery of vectors, low rank recovery of matrices and tensors, as well as low rank plus sparse recovery of matrices, i.e., robust PCA. |
| Researcher Affiliation | Academia | Ying Feng 1 David P. Woodruff 1 1Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA. Correspondence to: Ying Feng <yingfeng@andrew.cmu.edu>, David P. Woodruff <dwoodruf@cs.cmu.edu>. |
| Pseudocode | Yes | Algorithm 1 Recover-Vector(n, m, k), Algorithm 2 Fast-Recover(n, m, k), Algorithm 3 Estimate-L0(n, m, ε), Algorithm 4 Recover-Matrix(n, m, k), Algorithm 5 RPCA(n, m, k, r), Algorithm 6 Recover-tensor(n1, nd, m, k) |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments involving datasets, therefore no dataset access information for training is provided. |
| Dataset Splits | No | This paper is theoretical and does not conduct experiments, thus no dataset split information is provided for validation. |
| Hardware Specification | No | This paper is theoretical and does not describe experiments with specific hardware, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper mentions general algorithms and functions (e.g., AES, SHA256) but does not provide specific ancillary software details with version numbers needed to replicate any experimental setup, as it is a theoretical paper. |
| Experiment Setup | No | This paper is theoretical and does not describe experiments, therefore no experimental setup details such as hyperparameters or training configurations are provided. |