9 papers · 1 filter
Private Graph Property Testing
Hendrik Fichtenberger, Abigail Gentle, Tamalika Mukherjee +1
Graph property testing asks whether a massive graph satisfies a given property, or is far from doing so, using only a sublinear number of queries to the graph. Since property teste…
Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model
Rachel Cummings, Alessandro Epasto, Jieming Mao +3
The turnstile continual release model of differential privacy captures scenarios where a privacy-preserving real-time analysis is sought for a dataset evolving through additions an…
Sublinear Space Graph Algorithms in the Continual Release Model
Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee +1
The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of edge updates where new private solut…
Differential privacy and Sublinear time are incompatible sometimes
Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu +1
Differential privacy and sublinear algorithms are both rapidly emerging algorithmic themes in times of big data analysis. Although recent works have shown the existence of differen…
Differentially Private Clustering in Data Streams
Alessandro Epasto, Tamalika Mukherjee, Peilin Zhong
Clustering problems (such as -means and -median) are fundamental unsupervised machine learning primitives, and streaming clustering algorithms have been extensively studied i…
Differentially Private -Heavy Hitters in the Sliding Window Model
Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee +1
The data management of large companies often prioritize more recent data, as a source of higher accuracy prediction than outdated data. For example, the Facebook data policy retain…
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee +1
We develop a framework for efficiently transforming certain approximation algorithms into differentially-private variants, in a black-box manner. Specifically, our results focus on…
On computing Discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
Bhaskar DasGupta, Elena Grigorescu, Tamalika Mukherjee
Characterizing shapes of high-dimensional objects via Ricci curvatures plays a critical role in many research areas in mathematics and physics. However, even though several discret…
Privately Estimating Graph Parameters in Sublinear time
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee
We initiate a systematic study of algorithms that are both differentially private and run in sublinear time for several problems in which the goal is to estimate natural graph para…