69 citations · 85 across the 16 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.DS2023
Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs
Xiuge Chen, Rajesh Chitnis, Patrick Eades +1
In this paper, we design sub-linear space streaming algorithms for estimating three fundamental parameters -- maximum independent set, minimum dominating set and maximum matching -…
cs.DS2023
Maximum Coverage in Sublinear Space, Faster
Stephen Jaud, Anthony Wirth, Farhana Choudhury
Given a collection of sets from a universe , the Maximum Set Coverage problem consists of finding sets whose union has largest cardinality. This problem is NP-…
cs.CR2023
Tight Data Access Bounds for Private Top- Selection
Hao Wu, Olga Ohrimenko, Anthony Wirth
We study the top- selection problem under the differential privacy model: items are rated according to votes of a set of clients. We consider a setting in which algorithms c…