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

Cardinality sketches are compact data structures for representing sets or vectors. These sketches are space-efficient, typically requiring only logarithmic storage in the input size, and enable approximation of cardinality (or the number of nonzero entries). A crucial property in applications is composability of the sketching map, meaning that the sketch of a union of sets can be computed from individual sketches. Existing designs provide strong statistical guarantees, ensuring that a randomly sampled sketching map is accurate with high probability for a number of queries that is exponential in the sketch size \(k\). However, these guarantees degrade to quadratic in \(k\) when queries are adaptive, meaning they depend on previous responses.