A Framework for Adversarially Robust Streaming Algorithms
From MaRDI portal
Publication:5066953
DOI10.1145/3498334OpenAlexW3014289865MaRDI QIDQ5066953
David P. Woodruff, Eylon Yogev, Rajesh Jayaram, Omri Ben-Eliezer
Publication date: 31 March 2022
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3498334
Related Items (3)
Property-preserving hash functions for Hamming distance from standard assumptions ⋮ Mirror games against an open book player ⋮ Cuckoo hashing in cryptography: optimal parameters, robustness and applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An information statistics approach to data stream and communication complexity
- Finding repeated elements
- The space complexity of approximating the frequency moments
- Finding frequent items in data streams
- Separating adaptive streaming from oblivious streaming using the bounded storage model
- A Tight Lower Bound for High Frequency Moment Estimation with Small Error
- Modern Computer Algebra
- Differential privacy under continual observation
- Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
- Sketching in Adversarial Environments
- Optimal Streaming and Tracking Distinct Elements with High Probability
- Bloom Filters in Adversarial Environments
- Deterministically Estimating Data Stream Frequencies
- The best constants in the Khintchine inequality
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Continuous Monitoring of l_p Norms in Data Streams
- High Probability Frequency Moment Sketches
- Separations and equivalences between turnstile streaming and linear sketching
- The Data Stream Space Complexity of Cascaded Norms
- Sublinear Algorithms for (Δ + 1) Vertex Coloring
- Turnstile streaming algorithms might as well be linear sketches
- How robust are linear sketches to adaptive inputs?
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Pseudo-Deterministic Streaming.
- Adversarial laws of large numbers and optimal regret in online classification
This page was built for publication: A Framework for Adversarially Robust Streaming Algorithms
