CMU Theory Lunch: Or Sheffet, Clustering under Stability Assumptions/title>  <link rel="stylesheet" href="lunch-main.css"/> </head> <body> <div id="page"> <div id="page_contents">  <div id="header"> <div id="page_title">Theory Lunch</div> <div id="scs_logo"><img src="cmu-scs.gif" alt="School of Computer Science, Carnegie Mellon University" width="290px" border="0" /></div> </div> <div id="main_container">  <div id="sched_header"> Efficient Computation under the Constraints of Privacy and Incentives </div> <div id="abs_talk_speaker">Aaron Roth </a> </div> <div id="abs_date">Feb 10, 2010</div>  <div id="abs">  <p>ABSTRACT: In a networked world, both data ownership and computation are increasingly distributed. Algorithms are therefore facing constraints stemming from both the source of their inputs, as well as the identity of those performing their computations. In this talk, I will discuss foundational results concerning two particularly important such constraints: the need to protect the privacy of sensitive information, and the need to incentivize selfish users. </p><p> In the main portion of this talk, I will introduce and motivate differential privacy and present very recent work showing how to efficiently answer exponentially many statistical queries about an input data set in an online manner, while still provably protecting the privacy of individuals in the data set. I will also briefly discuss recent work on combinatorial optimization under the constraint of differential privacy, and in particular, how differential privacy can be viewed as a game theoretic solution concept. As a solution concept, differential privacy can be used to circumvent strong computational lower bounds for truthful mechanisms, and to construct mechanisms that do not require the exchange of money. </p><p> This will serve as a segue into the second portion of the talk: a brief survey of recent work aiming to develop computationally efficient solution concepts in game theory. In recent years, the study of the interplay between computation and incentive has lead to many impossibility results. For example, it is computationally difficult to compute Nash equilibria in general games, or to implement truthful mechanisms in some simple settings. Solution concepts are intended to be predictive, and thus should be plausibly implementable by computationally bounded agents. In addition to showing how differential privacy can be used to circumvent hardness results in mechanism design, I will discuss how approximate Nash equilibria can be efficiently computed in a slightly modified model, and how the analysis of efficient learning dynamics can be used to bound the price of anarchy in repeated games. </p><p> This is a practice job talk, so please come prepared to ask hostile questions. </p> </div>  </body>