The ISR Seminar Series Presents:
 
Rachel Greenstadt, Harvard University
 
Title: SSDPOP: Privatizing Constraint Optimization
 
Thursday, December 7th, 2006
12pm
NSH-1305
Lunch will be served
 

ABSTRACT:
Multi-agent systems designed to assist people or work
collaboratively with them require that people reveal private
information.  For people to entrust private information to such
systems, they will want assurance that this information will be
protected and that they will receive accurate characterization of the
extent to which it will be.  Distributed Constraint Optimization
(DCOP) has emerged as a prominent technique for multiagent
coordination; however, existing algorithms for solving DCOP problems
do not adequately protect agents' private information.  This talk
provides an analysis of the ways in which privacy has been protected
and lost in existing DCOP algorithms.  Based on this analysis it
presents a new algorithm, SSDPOP, which augments DPOP, a prominent
DCOP algorithm, with secret sharing techniques.  This approach
significantly reduces privacy loss, while simultaneously preserving
the structure of the DPOP algorithm and introducing only minimal
computational overhead.  Results show that SSDPOP reduces privacy loss
by 29-88\% on average over DPOP according to the VPS metrics EntropyTS
and $D|A$.  SSDPOP requires only two additional rounds of
communication and a polynomial-time computation, both of which can be
performed as a preprocessing step before the optimization.
 
BIO: 
Rachel Gareenstadt is a 5th and final year Ph.D. candidate in
Computer Science at Harvard University, advised by Michael D. Smith.
Her research interests lie at the intersection of privacy and
multi-agent systems.  Her thesis aims to analyze the privacy
properties of current distributed constraint optimization algorithms
and design new algorithms that perform better with respect to privacy.
Previously, she was a Dept of Homeland Security fellow and, before
that, a M.Eng student at MIT.  Her previous work examined privacy in
the context of e-commerce, regulatory regimes and electronic health
care, as well as the application of DRM technology to privacy
problems, covert channels and steganography.  She enjoys hiking in her
spare time.