Security and Privacy Applied Research Lab

Optimizing Sensing: Challenges for Security and Privacy

Andreas Krause
Carnegie Mellon University


Where should we place sensors to quickly detect contamination in drinking water distribution networks? Which data should we acquire about web surfers in order to improve personalized search? These problems share a fundamental challenge: How can we obtain the most useful information about the state of the world, at minimum cost?

Such sensing, or active learning, problems are typically NP-hard, and were commonly addressed using heuristics without theoretical guarantees about the solution quality. In this talk, I will present algorithms which efficiently find provably near-optimal solutions to large, complex sensing problems. Our algorithms exploit submodularity, an intuitive notion of diminishing returns, common to many sensing problems; the more sensors we have already deployed, the less we learn by placing another sensor. In addition to identifying the most informative observations, our algorithms allow to address important security and privacy challenges arising in practical sensing problems. In security-critical applications such as protecting drinking water from contamination, the sensor placements need to be robust against adversaries and sensor failures. In the web search example, acquired data about users should enable effective personalization, while minimizing the incursion in privacy.

I will also present results applying our algorithms to several real-world sensing tasks, including environmental monitoring using robotic sensors, trading off utility and privacy in personalized search, and a sensor placement competition.

This talk is mainly based on joint work with Carlos Guestrin and Eric Horvitz.


Andreas Krause is a Ph.D. Candidate at the Computer Science Department of Carnegie Mellon University. He is a recipient of a Microsoft Research Graduate Fellowship, and his research on sensor placement and information acquisition received awards at several conferences (KDD '07, IPSN '06, ICML '05 and UAI '05). He obtained his Diplom in Computer Science and Mathematics from the Technische Universität München, where his research received the NRW Undergraduate Science Award. He has accepted a tenure-track position at the California Institute of Technology and will join their Computer Science faculty in January 2009.