Mihir Singhal

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries

Cardinality sketches are compact data structures that efficiently estimate the number of distinct elements across multiple queries while minimizing storage, communication, and computational costs. However, recent research has shown that these sketches can fail under {\em adaptively chosen queries},…