45 citations · 115 across the 24 of their papers we have counts for
27 papers · 1 filter
Subgraph Counting with Local Node Differential Privacy
Sofya Raskhodnikova, Adam Smith, Connor Wagaman +1
We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analys…
Testing Connectedness and Edge Connectedness
Diptaksho Palit, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova +1
We revisit the classical problem of testing connectedness of graphs represented in the adjacency lists model and obtain optimal bounds. Specifically, we show that -tes…
Query Complexity of Testing Structured Parenthesis Languages
Tim Jackman, Diptaksho Palit, Sofya Raskhodnikova
We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query access to a word…
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…