Rigorous Systems Research Group (RSRG) Seminar

The increasing ubiquity of large-scale infrastructures for surveillance and data analysis has made understanding the impact of privacy a pressing priority. We propose a framework for studying a fundamental cost vs. privacy tradeoff in dynamic decision-making problems. The central question is: how can a decision maker take actions that are efficient for her goal, while simultaneously ensuring these actions do not inadvertently reveal her private information, even when observed and analyzed by a powerful adversary? We will examine two well-known decision problems (path planning and online learning), and in both cases establish sharp, information-theoretic complexity vs. privacy tradeoff. As a by-product, our analysis also leads to simple yet provably efficient algorithms for both the decision maker and eavesdropping adversary. Based in part on joint work with Mine Su Erturk (Stanford GSB), John N. Tsitsiklis (MIT LIDS) and Zhi Xu (MIT LIDS).