- Private Analysis of Graphs
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in October 2013
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:
Created by Ilya Razenshteyn at Wednesday, September 25, 2013 at 10:44 PM.