69 citations · 85 across the 16 of their papers we have counts for
20 papers
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 -…
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-…
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…
Single Round-trip Hierarchical ORAM via Succinct Indices
William Holland, Olga Ohrimenko, Anthony Wirth
Access patterns to data stored remotely create a side channel that is known to leak information even if the content of the data is encrypted. To protect against access pattern leak…
Walking to Hide: Privacy Amplification via Random Message Exchanges in Network
Hao Wu, Olga Ohrimenko, Anthony Wirth
The *shuffle model* is a powerful tool to amplify the privacy guarantees of the *local model* of differential privacy. In contrast to the fully decentralized manner of guaranteeing…
Randomize the Future: Asymptotically Optimal Locally Private Frequency Estimation Protocol for Longitudinal Data
Olga Ohrimenko, Anthony Wirth, Hao Wu
Longitudinal data tracking under Local Differential Privacy (LDP) is a challenging task. Baseline solutions that repeatedly invoke a protocol designed for one-time computation lead…