Aaron Roth

Photo of me

About Me

I am a Raj and Neera Singh Assistant Associate Professor of Computer and Information Science at the University of Pennsylvania computer science department, associated with the theory group, our new program in Networked and Social Systems Engineering, and the Warren Center for Network and Data Sciences. I am also affilied with the AMCS program (Applied Mathematics and Computational Science). I spent a year as a postdoc at Microsoft Research New England. Before that, I received my PhD from Carnegie Mellon University, where I was fortunate to have been advised by Avrim Blum. My main interests are in algorithms and theoretical computer science, and specifically in the area of database privacy, game theory and mechanism design, and learning theory. I am the recipient of a Presidential Early Career Award for Scientists and Engineers (PECASE), an Alfred P. Sloan Research Fellowship, an NSF CAREER award, and a Yahoo Academic Career Enhancement award.

For more information on my research interests, see my Research Statement and CV.

My lovely wife Cathy just got her PhD in math at MIT. At her insistence, I link to her website

Contact Information

Office: Levine 603
Phone: 215-746-6171
Email: aar...@cis.upenn.edu (Click to reveal my email address)

Teaching

Previous courses:
I'm fortunate to be able to work with several excellent graduate students and postdocs.
Current: Alumni:
Professional Activities

Workshops and Tutorials: Program Committee Member For:
Books and Surveys
  1. The Algorithmic Foundations of Differential Privacy. Joint with Cynthia Dwork. Foundations and Trends in Theoretical Computer Science, NOW Publishers. 2014.
  2. Privacy and Mechanism Design. Joint with Mallesh Pai. SIGecom Exchanges, 2013.

Recent and Selected Publications
 (See here for all publications, or my Google Scholar profile)
Click for abstract/informal discussion of results
  1. Privacy Odometers and Filters: Pay-as-you-Go Composition. Joint with Ryan Rogers, Jon Ullman, and Salil Vadhan. Manuscript.
  2. Fairness in Learning: Classic and Contextual Bandits. Joint with Matthew Joseph, Jamie Morgenstern, and Michael Kearns. Manuscript.
  3. Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing. Joint with Ryan Rogers, Adam Smith, and Om Thakkar. Manuscript.
  4. Robust Mediators in Large Games. Joint with Michael Kearns, Mallesh Pai, Ryan Rogers, and Jon Ullman. Manuscript. (This paper subsumes both "Mechanism Design in Large Games: Incentives and Privacy" which appeared in ITCS 2014, and "Asymptotically Truthful Equilibrium Selection" which appeared in EC 2014).
  5. Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs. Joint work with Shahin Jabbari, Ryan Rogers, and Steven Wu. Manuscript.
  6. The Strange Case of Privacy in Equilibrium Models. Joint work with Rachel Cummings, Katrina Ligett, and Mallesh Pai. To appear in EC 2016.
  7. Adaptive Learning with Robust Generalization Guarantees. Joint with Rachel Cummings, Katrina Ligett, Kobbi Nissim, and Steven Wu. To appear in COLT 2016.
  8. Do Prices Coordinate Markets?. Joint work with Justin Hsu, Jamie Morgenstern, Ryan Rogers, and Rakesh Vohra. To appear in STOC 2016.
  9. Watch and Learn: Optimizing from Revealed Preferences Feedback. Joint with Jon Ullman and Steven Wu. To appear in STOC 2016.
  10. Private Algorithms for the Protected in Social Network Search. Joint with Michael Kearns, Steven Wu, and Grigory Yaroslavtsev. In Proceedings of the National Academy of Sciences (PNAS), January 2016.
  11. Coordination Complexity: Small Information Coordinating Large Populations. Joint with Rachel Cummings, Katrina Ligett, Jaikumar Radhakrishnan and Steven Wu. In the proceedings of ITCS 2016.
  12. Jointly Private Convex Programming. Joint work with Justin Hsu, Zhiyi Huang, and Steven Wu. In the proceedings of SODA 2016.
  13. Generalization in Adaptive Data Analysis and Holdout Reuse. Joint work with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, and Omer Reingold. In the proceedings of NIPS 2015.
  14. The Reusable Holdout: Preserving Validity in Adaptive Data Analysis. Joint work with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, and Omer Reingold. In Science, August 7 2015.
  15. Inducing Approximately Optimal Flow Using Truthful Mediators. Joint work with Ryan Rogers, Jonathan Ullman, and Steven Wu. In the proceedings of EC 2015.
  16. Private Pareto Optimal Exchange. Joint with Sampath Kannan, Jamie Morgenstern, and Ryan Rogers. In the proceedings of EC 2015.
  17. Preserving Statistical Validity in Adaptive Data Analysis. Joint work with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, and Omer Reingold. In the proceedings of STOC 2015.
  18. Online Learning and Profit Maximization from Revealed Preferences. Joint with Kareem Amin, Rachel Cummings, Lili Dworkin, and Michael Kearns. In the proceedings of AAAI 2015.
  19. Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy). Joint with Sampath Kannan, Jamie Morgenstern, and Steven Wu. In the proceedings of SODA 2015.
  20. Dual Query: Practical Private Query Release for High Dimensional Data. Joint work with Marco Gaboradi, Emilio Jesús Gallego Arias, Justin Hsu, and Steven Wu. In the proceedings of ICML 2014.
  21. Bounds for the Query Complexity of Approximate Equilibria. Joint work with Paul Goldberg In the proceedings of EC 2014.
    Invited to a special issue of the ACM Transactions on Economics and Computation (TEAC) 2015.
  22. Private Matchings and Allocations. Joint work with Justin Hsu, Zhiyi Huang, Tim Roughgarden, and Steven Wu. In the proceedings of STOC 2014.
  23. Beyond Worst-Case Analysis in Private Singular Vector Computation. Joint with Moritz Hardt. In the proceedings of STOC 2013.
  24. Differential Privacy for the Analyst via Private Equilibrium Computation. Joint with Justin Hsu and Jon Ullman. In the proceedings of STOC 2013.
  25. Privately Releasing Conjunctions and the Statistical Query Barrier. Joint with Anupam Gupta, Moritz Hardt, and Jonathan Ullman. In the proceedings of STOC 2011.
    Full version appears in SIAM Journal on Computing (SICOMP) 2013.
  26. Selling Privacy at Auction. Joint work with Arpita Ghosh. In the proceedings of EC 2011.
    Invited to a special issue of Games and Economic Behavior (GEB) 2013.
  27. Interactive Privacy via the Median Mechanism. Joint with Tim Roughgarden. In the proceedings of STOC 2010.
  28. A Learning Theory Approach to Non-Interactive Database Privacy. Joint with Avrim Blum and Katrina Ligett. In the proceedings of STOC 2008: The 40th ACM Symposium on the Theory of Computing.
    Full version appears in Journal of the ACM (JACM) 2013.
  29. Regret Minimization and the Price of Total Anarchy. Joint with Avrim Blum, MohammadTaghi Hajiaghayi, and Katrina Ligett. In the proceedings of STOC 2008: The 40th ACM Symposium on the Theory of Computing.
Presentations
(Slides Available Upon Request)