Private Analysis of Graphs

Speaker: Sofya Raskhodnikova

Date: Wednesday, October 02, 2013

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host:

Contact: Ilya Razenshteyn, ilyaraz@csail.mit.edu

Relevant URL: http://www.ilyaraz.org/acseminar

Speaker URL: None

Speaker Photo:
None

Reminders to: compalgsem@lists.csail.mit.edu, theory-seminars@lists.csail.mit.edu

Reminder Subject: TALK: Private Analysis of Graphs

We discuss algorithms for the private analysis of network data. Such algorithms work on data sets that contain sensitive relationship information (for example, romantic ties). Their goal is to compute approximations to global statistics of the graph while protecting information specific to individuals. Our algorithms satisfy a rigorous notion of privacy, called node differential privacy. Intuitively, it means that an algorithm's output distribution does not change significantly when a node and all its adjacent edges are removed from a graph. We present several techniques for designing node differentially private algorithms. We also develop methodology for analyzing the accuracy of such algorithms on realistic networks. Our techniques are based on combinatorial analysis, network flow, and linear and convex programming.

Based on joint work with Shiva Kasiviswanathan, Kobbi Nissim and Adam Smith.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Ilya Razenshteyn at Wednesday, September 25, 2013 at 10:44 PM.