Cover Image

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cohen, Edith, Nelson, Jelani, Sarlós, Tamás, Singhal, Mihir, Stemmer, Uri
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)

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

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)

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

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

Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries
by: Cohen, Edith, et al.
Published: (2024)

Tight bounds for stream decodable error-correcting codes
by: Gupta, Meghal, et al.
Published: (2024)

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

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

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
by: Azarmehr, Amir, et al.
Published: (2025)

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

Optimal quantile estimation: beyond the comparison model
by: Gupta, Meghal, et al.
Published: (2024)

Locally computing edge orientations
by: Mitrović, Slobodan, et al.
Published: (2025)

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

Tight Static Lower Bounds for Non-Adaptive Data Structures
by: Persiano, Giuseppe, et al.
Published: (2020)

Terminal Embeddings in Sublinear Time
by: Cherapanamjeri, Yeshwanth, et al.
Published: (2021)

Tight Bounds for Online Scheduling in the One-Fast-Many-Slow Machines Setting
by: Jeang, John, et al.
Published: (2026)

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

Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
by: Chua, Lynn, et al.
Published: (2026)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
by: Mitrović, Slobodan, et al.
Published: (2026)

(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
by: Trabelsi, Ohad
Published: (2023)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Tight Bounds for Classical Open Addressing
by: Bender, Michael A., et al.
Published: (2024)

Adaptive BSTs for Single-Source and All-to-All Requests: Algorithms and Lower Bounds
by: Shiran, Maryam
Published: (2025)

Almost Tight Bounds for Online Hypergraph Matching
by: Tröbst, Thorben, et al.
Published: (2024)

Nearly Tight Bounds for the Online Sorting Problem
by: Azar, Yossi, et al.
Published: (2025)

Tight Bounds for Sorting Under Partial Information
by: van der Hoog, Ivor, et al.
Published: (2024)

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

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
by: Kosolobov, Dmitry
Published: (2024)

Almost Tight Bounds for Differentially Private Densest Subgraph
by: Dinitz, Michael, et al.
Published: (2023)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
by: Kuszmaul, William, et al.
Published: (2024)

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

Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models
by: Bishnu, Arijit, et al.
Published: (2025)

Space Complexity of Minimum Cut Problems in Single-Pass Streams
by: Ding, Matthew, et al.
Published: (2024)

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
by: Shah, Vihan
Published: (2026)

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
by: Im, Sungjin, et al.
Published: (2025)