Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs

Edith Cohen, Jelani Nelson, Tamás Sarlós +1

CountSketch and Feature Hashing (the "hashing trick") are popular randomized dimensionality reduction methods that support recovery of ${\ell }_2$-heavy hitters (keys $i$ where $v_i^2…