Franklin

Staff View

LEADER 03464cam a2200481 4500
005 20150326165427.0
006 m d
007 cr_|n---____
008 140312s2013 ||||||||o|||||||| ||eng d
001 9961468753503681
020
  
  
a| 9781303145933
035
  
  
a| DISSAAI3565090
035
  
  
a| AAI3565090
035
  
  
a| (PU)6146875-penndb-Voyager
040
  
  
a| UMI c| UMI
100
1
  
a| Huang, Zhiyi.
245
1
0
a| New techniques for computation over private data h| [electronic resource].
300
  
  
a| 180 p. b|
502
  
  
a| Thesis (Ph.D. in Computer and Information Science) -- University of Pennsylvania, 2013.
538
  
  
a| Mode of access: World Wide Web.
500
  
  
a| Source: Dissertation Abstracts International, Volume: 74-10(E), Section: B.
500
  
  
a| Advisers: Sampath Kannan; Aaron Roth.
506
  
  
a| Restricted for use by site license.
520
  
  
a| 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.
520
  
  
a| 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.
520
  
  
a| 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.
530
  
  
a| Also available in print.
590
  
  
a| School code: 0175.
650
  
0
a| Computer science
690
  
  
a| 0984
650
  
4
a| Penn dissertations x| Computer and Information Science.
650
  
4
a| Computer and Information Science x| Penn dissertations.
700
1
  
a| Roughgarden, Tim, e| committee member
700
1
  
a| Khanna, Sanjeev e| committee member
700
1
  
a| Kearns, Michael e| committee member
700
1
  
a| Guha, Sudipto e| committee member
700
1
  
a| Roth, Aaron, e| advisor
700
1
  
a| Kannan, Sampath, e| advisor
710
2
  
a| University of Pennsylvania. b| Computer and Information Science.
773
0
  
t| Dissertation Abstracts International g| 74-10B(E).
790
  
  
a| 0175
791
  
  
a| Ph.D.
792
  
  
a| 2013
856
4
0
u| http://hdl.library.upenn.edu/1017.12/1274290 z| Connect to full text