3 papers
cs.DS2025
Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
Edith Cohen, Mihir Singhal, Uri Stemmer
Cardinality sketches are compact data structures that efficiently estimate the number of distinct elements across multiple queries while minimizing storage, communication, and comp…
cs.DS2025
Locally computing edge orientations
Slobodan Mitrović, Ronitt Rubinfeld, Mihir Singhal
We consider the question of orienting the edges in a graph such that every vertex has bounded out-degree. For graphs of arboricity , there is an orientation in which every v…
cs.DS2024
One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
Edith Cohen, Jelani Nelson, Tamás Sarlós +2
Cardinality sketches are compact data structures for representing sets or vectors. These sketches are space-efficient, typically requiring only logarithmic storage in the input siz…