8 papers · 1 filter
Fully Dynamic Graph Algorithms with Edge Differential Privacy
Sofya Raskhodnikova, Teresa Anna Steiner
We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates, where edges are inserted and deleted ove…
Local Node Differential Privacy
Sofya Raskhodnikova, Adam Smith, Connor Wagaman +1
We initiate an investigation of node differential privacy for graphs in the local model of private data analysis. In our model, dubbed LNDP*, each node sees its own edge list and r…
Homomorphism Testing with Resilience to Online Manipulations
Esty Kelman, Uri Meir, Debanuj Nayak +1
A central challenge in property testing is verifying algebraic structure with minimal access to data. A landmark result addressing this challenge, the linearity test of Blum, Luby,…
Fast Agnostic Learners in the Plane
Talya Eden, Ludmila Glinskih, Sofya Raskhodnikova
We investigate the computational efficiency of agnostic learning for several fundamental geometric concept classes in the plane. While the sample complexity of agnostic learning is…
Triangle Counting with Local Edge Differential Privacy
Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova +1
Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study tri…
Privately Evaluating Untrusted Black-Box Functions
Ephraim Linder, Sofya Raskhodnikova, Adam Smith +1
We provide tools for sharing sensitive data when the data curator does not know in advance what questions an (untrusted) analyst might ask about the data. The analyst can specify a…