How to Compute over Private Data


January 31, 2013


Zhiyi Huang


University of Pennsylvania


Over the past decade, rapid development in computing technology and the Internet has given rise to new challenges in large-scale computational problems. In particular, many computational problems that arise from electronic commerce rely on the private data of self-interested agents. So the algorithms not only need to deal with usual computational resource limitations but also the new constraints imposed by social, economic, and personal considerations.

On the one hand, algorithmic mechanism design studies the game-theoretic perspective of private data, aiming to incentivize truthful behavior by ensuring that truth-telling maximizes the “one-shot” utilities of the agents, i.e., the utilities directly generated from the outcome of the mechanism. On the other hand, differential privacy considers the privacy perspective of private data, focusing on the agents’ concern on the potential leak of their private data by the mechanism, which may harm their utilities in the future. Finally, there has been a recent direction of research aiming to handle both perspectives simultaneously by combining the techniques from both fields.

In this talk, I will give an overview of my contributions to these three topics. (1) For the game-theoretic perspective, we advance the technique of black-box reductions in mechanism design, reducing a large family of mechanism design problems to the better-understood algorithm design problems, including all problems in Bayesian setting and all single-parameter and symmetric problems in prior-free setting. (2) For the privacy perspective, we introduce the technique of low-sensitivity metric embedding and propose efficient and differentially private mechanisms for a sub-class of query release problems. Our result is among the first to circumvent the known impossibility results for general query release problems. (3) Finally, we propose the first general technique for designing mechanisms that handle both the game-theoretic and the privacy perspectives simultaneously for any mechanism design problems.


Zhiyi Huang

Zhiyi Huang is a graduate student in computer and information science at University of Pennsylvania, advised by Sampath Kannan and Aaron Roth.
His research interests mainly focus on algorithmic game theory, differential privacy, and online algorithms. Zhiyi is a recipient of the Simons Graduate Fellowship in Theoretical Computer Science. He received his bachelor’s degree from Tsinghua University in 2008, where he attended the first “Yao Class” under Andrew Yao. He enrolled in the computer and information science PhD program at Penn in the fall of 2008, with an expected graduation date of May 2013.