Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness

Elena Gribelyuk, Honghao Lin, David P. Woodruff +2

We introduce a novel technique for ``lifting'' dimension lower bounds for linear sketches in the real-valued setting to dimension lower bounds for linear sketches with polynomially…