How robust are linear sketches to adaptive inputs?

DOI10.1145/2488608.2488624MaRDI QIDQ5495782zbMATH OpenOpenAlexFDO

Authors Moritz Hardt, David P. Woodruff

Publication date 7 August 2014

Published in Proceedings of the forty-eighth 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

compressed sensingrobustnesssketches

Mathematics Subject Classification ID

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

Abstract: Linear sketches are powerful algorithmic tools that turn an n-dimensional input into a concise lower-dimensional representation via a linear transformation. Such sketches have seen a wide range of applications including norm estimation over data streams, compressed sensing, and distributed computing. In almost any realistic setting, however, a linear sketch faces the possibility that its inputs are correlated with previous evaluations of the sketch. Known techniques no longer guarantee the correctness of the output in the presence of such correlations. We therefore ask: Are linear sketches inherently non-robust to adaptively chosen inputs? We give a strong affirmative answer to this question. Specifically, we show that no linear sketch approximates the Euclidean norm of its input to within an arbitrary multiplicative approximation factor on a polynomial number of adaptively chosen inputs. The result remains true even if the dimension of the sketch is d = n - o(n) and the sketch is given unbounded computation time. Our result is based on an algorithm with running time polynomial in d that adaptively finds a distribution over inputs on which the sketch is incorrect with constant probability. Our result implies several corollaries for related problems including lp-norm estimation and compressed sensing. Notably, we resolve an open problem in compressed sensing regarding the feasibility of l2/l2-recovery guarantees in the presence of computationally bounded adversaries.

Recommendations

• Sketching in Adversarial Environments
• On deterministic sketching and streaming for sparse recovery and norm estimation
• On deterministic sketching and streaming for sparse recovery and norm estimation
• Efficient sketches for the set query problem
• Sketching as a tool for numerical linear algebra

Cited in

(14)

• Robust property-preserving hash functions for Hamming distance and more
• Separating adaptive streaming from oblivious streaming using the bounded storage model
• Property-preserving hash functions for Hamming distance from standard assumptions
• High probability frequency moment sketches
• A Framework for Adversarially Robust Streaming Algorithms
• Adversarially robust property-preserving hash functions
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• 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
• Adversarially robust streaming algorithms via differential privacy
• A framework for adversarial streaming via differential privacy and difference estimators
• Finding missing items requires strong forms of randomness
• Adversarial laws of large numbers and optimal regret in online classification

This page was built for publication: How robust are linear sketches to adaptive inputs?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495782)