BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/465
DTSTAMP:20230914T125925Z
SUMMARY:Private Analysis of Graphs
DESCRIPTION:Speaker: Adam Smith (The Pennsylvania State University & Boston
University)\n\nAbstract: \nWe 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 not
ion 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. A key compone
nt of our work is the design of efficiently computable Lipschitz extension
s of commonly computed graph statistics. Given a graph statistic f\, we se
ek to design a new function g that is efficiently computable and "robust"
to the addition or removal of vertices\, yet agrees with f on as large a s
et of graphs as possible. Our techniques are based on combinatorial analys
is\, network flow\, and linear and convex programming. Based on joint work
with Shiva Kasiviswanathan\, Kobbi Nissim and Sofya Raskhodnikova. Bio: A
dam Smith is an associate professor in the Department of Computer Science
and Engineering at Penn State\; currently\, he is on sabbatical at Boston
University. His research interests lie in cryptography\, privacy and their
connections to information theory\, quantum computing and statistics. He
received his Ph.D. from MIT in 2004 and was subsequently a visiting schola
r at the Weizmann Institute of Science and UCLA.\n
URL:https://www.tcs.tifr.res.in/web/events/465
DTSTART;TZID=Asia/Kolkata:20140225T160000
DTEND;TZID=Asia/Kolkata:20140225T170000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR