English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

CountSketch and Feature Hashing (the "hashing trick") are popular randomizeddimensionality reduction methods that support recovery of $\ell_2$-heavyhitters (keys $i$ where $v_i^2 > \epsilon \|\boldsymbol{v}\|_2^2$) andapproximate inner products. When the inputs are {\em not adaptive} (do notdepend on prior outputs), classic estimators applied to a sketch of size$O(\ell/\epsilon)$ are accurate for a number of queries that is exponential in$\ell$. When inputs are adaptive, however, an adversarial input can beconstructed after $O(\ell)$ queries with the classic estimator and the bestknown robust estimator only supports $\tilde{O}(\ell^2)$ queries. In this workwe show that this quadratic dependence is in a sense inherent: We design anattack that after $O(\ell^2)$ queries produces an adversarial input vectorwhose sketch is highly biased. Our attack uses "natural" non-adaptive inputs(only the final adversarial input is chosen adaptively) and universally applieswith any correct estimator, including one that is unknown to the attacker. Inthat, we expose inherent vulnerability of this fundamental method.

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