Cover Image

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs

Fuente: arXiv

Saved in:

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

Similar Items

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

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
by: Ahmadian, Sara, 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)

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

QSketch: An Efficient Sketch for Weighted Cardinality Estimation in Streams
by: Qi, Yiyan, et al.
Published: (2024)

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

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

Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information
by: Gadekar, Ameet, et al.
Published: (2025)

On Differential Privacy for Adaptively Solving Search Problems via Sketching
by: Feng, Shiyuan, et al.
Published: (2025)

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

Max-Cut with Multiple Cardinality Constraints
by: Makarychev, Yury, et al.
Published: (2025)

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
by: Xu, Chao, et al.
Published: (2026)

Average-Distortion Sketching
by: Bao, Yiqiao, et al.
Published: (2024)

On Sketching Trimmed Statistics
by: Lin, Honghao, et al.
Published: (2025)

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

Fast Similarity Sketching
by: Dahlgaard, Søren, et al.
Published: (2017)

LMQ-Sketch: Lagom Multi-Query Sketch for High-Rate Online Analytics
by: Hilgendorf, Martin, et al.
Published: (2025)

The Case for External Graph Sketching
by: Bender, Michael A., et al.
Published: (2025)

Sketching and Streaming for Dictionary Compression
by: Becker, Ruben, et al.
Published: (2023)

Sketching Cuts in Graphs and Hypergraphs
by: Kogan, Dmitry, et al.
Published: (2014)

Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments
by: Ansaripour, Matin, et al.
Published: (2024)

Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation
by: Barak, Zohar, et al.
Published: (2026)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
by: Doron-Arad, Ilan, et al.
Published: (2023)

Fast Sampling Based Sketches for Tensors
by: Swartworth, William, et al.
Published: (2024)

Approximating Tensor Network Contraction with Sketches
by: Heddes, Mike, et al.
Published: (2026)

Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited
by: Mehlhorn, Kurt, et al.
Published: (2026)

Almost Linear Size Edit Distance Sketch
by: Koucký, Michal, et al.
Published: (2024)

Fast and Compact Sketch-Based Dynamic Connectivity
by: De Man, Quinten, et al.
Published: (2025)

Elastic Sketch under Random Stationary Streams: Limiting Behavior and Near-Optimal Configuration
by: Mazziane, Younes Ben, et al.
Published: (2026)

SimiSketch: Efficiently Estimating Similarity of streaming Multisets
by: Dong, Fenghao, et al.
Published: (2024)

Multipass Linear Sketches for Geometric LP-Type Problems
by: Çekirge, N. Efe, et al.
Published: (2025)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
by: Gribelyuk, Elena, et al.
Published: (2025)

MagnifierSketch: Quantile Estimation Centered at One Point
by: Guo, Jiarui, et al.
Published: (2025)

Targeted Least Cardinality Candidate Key for Relational Databases
by: Nakos, Vasileios, et al.
Published: (2024)

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
by: Kurita, Kazuhiro, et al.
Published: (2022)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)

Carbonyl4: A Sketch for Set-Increment Mixed Updates
by: Zhao, Yikai, et al.
Published: (2024)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
by: Sawettamalya, Pachara, et al.
Published: (2025)

Sampling Methods for Inner Product Sketching
by: Daliri, Majid, et al.
Published: (2023)

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