How robust are linear sketches to adaptive inputs?

DOI10.1145/2488608.2488624zbMath1293.68291arXiv1211.1056OpenAlexW1988355221MaRDI QIDQ5495782

David P. Woodruff, Moritz Hardt

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.1056

zbMATH Keywords

robustnesscompressed sensingsketches

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Separating adaptive streaming from oblivious streaming using the bounded storage model ⋮ Bloom Filters in Adversarial Environments ⋮ A Framework for Adversarially Robust Streaming Algorithms ⋮ Property-preserving hash functions for Hamming distance from standard assumptions ⋮ Cuckoo hashing in cryptography: optimal parameters, robustness and applications ⋮ Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols ⋮ Bet-or-pass: adversarially robust Bloom filters ⋮ High Probability Frequency Moment Sketches ⋮ Unnamed Item ⋮ Robust property-preserving hash functions for Hamming distance and more