  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.
