How to compute over private data

Speaker:        Zhiyi Huang
                University of Pennsylvania

Title:          "How to compute over private data"

Date:           Monday, 25 March 2013

Time:           4:00pm - 5:00pm

Venue:          Lecture Theatre F (near lifts 25/26), HKUST

Abstract:

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.

********************
Biography:

Zhiyi Huang is a graduate student in computer and information science at
University of Pennsylvania, advised by Prof. Sampath Kannan and Prof.
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.