Distributed Models for Private Analysis of Graph Data

I'll discuss models for distributed and private analysis of network data in which nodes retain control of their data. I'll focus particularly on the *local* node-private model, which is a good fit for distributed social network data. We provide the first formulation and systematic investigation of the model, design a new algorithmic framework tailored to it, and develop new lower bound techniques that show fundamental limitations on its power. Joint work with Sofya Raskhodnikova, Connor Wagaman, and Anatoly Zavyalov.