ARC Colloquium: Sofya Raskhodnikova (Penn State)

Video of this talk is available at:

Full collection of talk videos are available at:

Algorithms & Randomness Center (ARC)

Sofya Raskhodnikova - Penn State

Monday, November 7, 2016

Klaus 1116 East - 11am

Differentially Private Analysis of Graphs

Many types of data can be represented as graphs, where nodes correspond to individuals and edges capture relationships between them. Examples include datasets capturing “friendships” in an online social network, financial transactions, email communication, doctor-patient relationships, and romantic ties. On one hand, such datasets contain sensitive information about individuals. On the other hand, global information that can be gleaned from their analysis can provide significant benefits to society. Several naive attempts at anonymizing sensitive data by stripping obvious identifying information resulted in spectacular failures. In this talk, we discuss algorithms for analyzing network data that satisfy a rigourous notion of privacy called node differential privacy. We present several techniques for designing node differentially private algorithms, based on combinatorial analysis, network flow, and linear and convex programming. 

Based on joint work with A. Smith (FOCS 2016) and with S. Kasiwisvanathan, K. Nissim, A. Smith (TCC 2013) 

Sofya Raskhodnikova is an associate professor of Computer Science and Engineering at Penn State. Her research interests include sublinear-time algorithms, private data analysis, approximation algorithms, and randomized algorithms. She got her PhD from MIT in 2003. She has held visiting positions at the Hebrew University of Jerusalemthe Weizmann Institute of Sciencethe Institute for Pure and Applied MathematicsBoston University and Harvard University
Speaker's webpage: Sofya Raskhodnikova

Event Details


  • Monday, November 7, 2016
    11:00 am - 12:00 pm
Location: Klaus 1116 East

For More Information Contact

Dani Denton

denton at cc dot gatech dot edu