New techniques for computation over private data / Zhiyi Huang.

Format:

Book

Manuscript

Thesis/Dissertation

Author/Creator:

Huang, Zhiyi.

Contributor:

Kannan, Sampath, advisor.

Roth, Aaron, advisor.

Guha, Sudipto, committee member.

Kearns, Michael, committee member.

Khanna, Sanjeev, committee member.

Roughgarden, Tim, committee member.

University of Pennsylvania. Computer and Information Science.

Language:

English

Subjects (All):

Penn dissertations--Computer and Information Science.

Computer and Information Science--Penn dissertations.

Local Subjects:

Penn dissertations--Computer and Information Science.

Computer and Information Science--Penn dissertations.

Physical Description:

x, 170 pages ; 29 cm

Production:

2013.

Summary:

Rapid development in computing technology and the Internet has given rise to new challenges in large-scale computational problems. In particular, many problems that arise from electronic commerce rely on the private data of self-interested agents. So the algorithms need to deal with both limited computational resources and some new challenges imposed by social, economic, and personal considerations of the agents.

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 agents' utilities from the outcome of the mechanism. On the other hand, differential privacy considers the privacy perspective, focusing on the agents' concern on the potential leak of their private data, which may harm their utilities in the future. Finally, a recent direction of research considers handling both perspectives simultaneously.

Our contributions are threefold. (1) For the game-theoretic perspective, we advance the technique of black-box reductions in mechanism design by reducing mechanism design problems to the better-understood algorithm design problems for all problems in the Bayesian setting and all single-parameter and symmetric problems in the 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 answering distance queries. 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 can handle both the game-theoretic and the privacy perspectives simultaneously for any mechanism design problems.

Notes:

Advisers: Sampath Kannan; Aaron Roth.

Thesis (Ph.D. in Computer and Information Science) -- University of Pennsylvania, 2013.

Includes bibliographical references.

OCLC:

864912179