New techniques for computation over private data [electronic resource].

Huang, Zhiyi.
180 p.
Computer science
Local subjects:
Penn dissertations -- Computer and Information Science.
Computer and Information Science -- Penn dissertations.
System Details:
Mode of access: World Wide Web.
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.
Thesis (Ph.D. in Computer and Information Science) -- University of Pennsylvania, 2013.
Source: Dissertation Abstracts International, Volume: 74-10(E), Section: B.
Advisers: Sampath Kannan; Aaron Roth.
Local notes:
School code: 0175.
Roughgarden, Tim, committee member
Khanna, Sanjeev committee member
Kearns, Michael committee member
Guha, Sudipto committee member
Roth, Aaron, advisor
Kannan, Sampath, advisor
University of Pennsylvania. Computer and Information Science.
Contained In:
Dissertation Abstracts International 74-10B(E).
Access Restriction:
Restricted for use by site license.
Location Notes Your Loan Policy
Description Status Barcode Your Loan Policy