2 papers
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.CR2021
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…