Research map / Adversarial robustness and security / Certified and empirical robustness
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Construct an adversarial noise input from non-adaptive heavy-key-plus-random-tail queries | CountSketch heavy-hitter estimators, including unknown and state-maintaining correct estimators · CountSketch heavy hitters | attack queries to produce biased input: O(\ell^2) queries | Hurt |
| Use the universal attack with inner-product queries against a standard basis vector | Correct CountSketch inner-product estimators · CountSketch inner-product estimation | attack queries to produce biased input: O(\ell^2) queries | Hurt |
| Construct an adversarial input using random-tail queries | Correct AMS norm estimators · AMS norm estimation | attack queries to produce adversarial input: O(\xi \ell^2 \epsilon^2) | Hurt |
| Use the universal attack with estimator accuracy \epsilon = \Theta(1) and bias \xi = O(1) | AMS norm estimation · AMS norm estimation | attack queries to produce adversarial input: O(\ell^2) queries | Hurt |
| Use the universal attack with bias \xi = O(\epsilon) | AMS norm estimation · AMS norm estimation | attack queries to produce adversarial input: O(\ell^2 \epsilon^3) | Hurt |
| Use the universal attack with accuracy \epsilon = O(1/\sqrt{\ell}) | AMS norm estimation · AMS norm estimation | attack queries to produce adversarial input: O(\sqrt{\ell}) queries | Hurt |
Closest papers by meaning
- Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs (ICML 2024 · similarity 0.85)
- Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters (NeurIPS 2024 · similarity 0.84)
- HUANG: A Robust Diffusion Model-based Targeted Adversarial Attack Against Deep Hashing Retrieval (AAAI 2025 · similarity 0.84)
- MaxSketch: Robust Distinct Counting in Streams via Random Projections (NeurIPS 2026 · similarity 0.83)
- Closing the Gap: Achieving Better Accuracy-Robustness Tradeoffs against Query-Based Attacks (AAAI 2024 · similarity 0.83)
- The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.