1 citations · 1 across the 3 of their papers we have counts for
4 papers · 1 filter
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…
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 v…
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…