all InfoSec news
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs. (arXiv:2207.00956v1 [cs.DS])
July 5, 2022, 1:20 a.m. | Edith Cohen, Jelani Nelson, Tamás Sarlós, Uri Stemmer
cs.CR updates on arXiv.org arxiv.org
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 > \epsilon \|\boldsymbol{v}\|_2^2$) and
approximate inner products. When the inputs are {\em not adaptive} (do not
depend 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 be
constructed after $O(\ell)$ queries with the …
More from arxiv.org / cs.CR updates on arXiv.org
Jobs in InfoSec / Cybersecurity
SOC 2 Manager, Audit and Certification
@ Deloitte | US and CA Multiple Locations
Senior Security Specialist
@ Lely | Maassluis, Netherlands
IT Security Manager (Corporate Security) (REF822R)
@ Deutsche Telekom IT Solutions | Budapest, Hungary
Senior Security Architect
@ Cassa Centrale Banca - Credito Cooperativo Italiano | Trento, IT, 38122
Senior DevSecOps Engineer
@ Raft | Las Vegas, NV (Remote)
Product Manager - Compliance
@ Arctic Wolf | Remote - Colorado