Cover Image

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries

Fuente: arXiv

Saved in:

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

Similar Items

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

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)

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)

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

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

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

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

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

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
by: Bukov, Anton, et al.
Published: (2023)

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

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

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

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

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

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

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
by: Chen, Yixin, et al.
Published: (2025)

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

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

Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut
by: Baswana, Surender, et al.
Published: (2025)

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

Bin Packing under Random-Order: Breaking the Barrier of 3/2
by: Hebbar, Anish, et al.
Published: (2024)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
by: Adar, Tomer, et al.
Published: (2026)

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

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
by: Chuzhoy, Julia, et al.
Published: (2025)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2025)

Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs
by: Bai, Tian, et al.
Published: (2022)

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

Correlation Sketches for Approximate Join-Correlation Queries
by: Santos, Aécio, et al.
Published: (2021)

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

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

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

The communication complexity of distributed estimation
by: Gopalan, Parikshit, et al.
Published: (2025)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2024)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

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)