4 papers
Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
Slobodan MitroviÄ, Srikkanth Ramachandran, Ronitt Rubinfeld +1
In this work, we focus on designing an efficient Local Computation Algorithm (LCA) for the set cover problem, which is a core optimization task. The state-of-the-art LCA for comput…
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…
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…
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…