Cover Image

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ahmadian, Sara, Cohen, Edith, Stemmer, Uri
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
by: Rapoport, Emma, et al.
Published: (2025)

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
by: Cohen, Edith, et al.
Published: (2024)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
by: Ahmadian, Sara, et al.
Published: (2024)

Stochastic Matching via Local Sparsification
by: Ahmadian, Sara, et al.
Published: (2026)

Protecting the Undeleted in Machine Unlearning
by: Cohen, Aloni, et al.
Published: (2026)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
by: Li, Yi, et al.
Published: (2024)

Adaptively Robust Resettable Streaming
by: Cohen, Edith, et al.
Published: (2026)

Hot PATE: Private Aggregation of Distributions for Diverse Task
by: Cohen, Edith, et al.
Published: (2023)

Generalized Top-k Mallows Model for Ranked Choices
by: Haddadan, Shahrzad, et al.
Published: (2025)

A Simple and Robust Protocol for Distributed Counting
by: Cohen, Edith, et al.
Published: (2025)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
by: Danait, Ved, et al.
Published: (2025)

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
by: Jin, Yujia, et al.
Published: (2024)

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
by: Munteanu, Alexander, et al.
Published: (2024)

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
by: Fahrbach, Matthew, et al.
Published: (2024)

Learning the Positions in CountSketch
by: Li, Yi, et al.
Published: (2023)

Privately Estimating Black-Box Statistics
by: Steinke, Günter F., et al.
Published: (2025)

On Sketching Quadratic Forms
by: Andoni, Alexandr, et al.
Published: (2015)

Coresets for Multiple $\ell_p$ Regression
by: Woodruff, David P., et al.
Published: (2024)

Tight Bounds for Learning Polyhedra with a Margin
by: Patel, Shyamal, et al.
Published: (2026)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
by: Pham, Ninh, et al.
Published: (2025)

DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding Windows (Technical Report)
by: Wang, Yiping, et al.
Published: (2024)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
by: Woodruff, David P., et al.
Published: (2023)

Tight Differentially Private PCA via Matrix Coherence
by: d'Orsi, Tommaso, et al.
Published: (2025)

Clustering to Minimize Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2024)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Improved and Oracle-Efficient Online $\ell_1$-Multicalibration
by: Ghuge, Rohan, et al.
Published: (2025)

Turnstile $\ell_p$ leverage score sampling with applications
by: Munteanu, Alexander, et al.
Published: (2024)

A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
by: Gribelyuk, Elena, et al.
Published: (2024)

Sample-efficient Multiclass Calibration under $\ell_{p}$ Error
by: Bairaktari, Konstantina, et al.
Published: (2025)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
by: Woodruff, David P., et al.
Published: (2024)

A Broader View on Clustering under Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2025)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
by: Makarychev, Konstantin, et al.
Published: (2025)

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
by: Karpov, Nikolai, et al.
Published: (2025)

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
by: Fahrbach, Matthew, et al.
Published: (2025)

Matrix Product Sketching via Coordinated Sampling
by: Daliri, Majid, et al.
Published: (2025)

Optimal Matrix Sketching over Sliding Windows
by: Yin, Hanyan, et al.
Published: (2024)

Black-Box $k$-to-$1$-PCA Reductions: Theory and Applications
by: Jambulapati, Arun, et al.
Published: (2024)

On Differentially Private Linear Algebra
by: Kaplan, Haim, et al.
Published: (2024)

Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
by: Dereziński, Michał, et al.
Published: (2024)