Aaron Roth

Photo of me

About Me

I am a Raj and Neera Singh Assistant 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 an Alfred P. Sloan Research Fellowship, an NSF CAREER award, and a Yahoo Academic Career Enhancement award.

New! Our Differential Privacy book is now available!

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
This semester I am teaching NETS 412 -- Algorithmic Game Theory.

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.

Selected Publications (bias towards recent)
 (See here for all publications, or my Google Scholar profile)
Click for abstract/informal discussion of results
  1. Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs. Joint work with Shahin Jabbari, Ryan Rogers, and Steven Wu. Manuscript.
  2. Generalization in Adaptive Data Analysis and Holdout Reuse. Joint work with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, and Omer Reingold. Manuscript.
  3. Privacy for the Protected (Only). Joint with Michael Kearns, Steven Wu, and Grigory Yaroslavtsev. Manuscript.
  4. Watch and Learn: Optimizing from Revealed Preferences Feedback. Joint with Jon Ullman and Steven Wu. Manuscript.
  5. Computer-aided verification in mechanism design. Joint with Gilles Barthe, Marco Gaboardi, Emilio Jesus Gallego Arias, Justin Hsu, and Pierre-Yves Strub. Manuscript.
  6. Jointly Private Convex Programming. Joint work with Justin Hsu, Zhiyi Huang, and Steven Wu. Manuscript.
  7. Privacy and Truthful Equilibrium Selection for Aggregative Games. Joint with Rachel Cummings, Michael Kearns, and Steven Wu. Manuscript.
  8. Inducing Approximately Optimal Flow Using Truthful Mediators. Joint work with Ryan Rogers, Jonathan Ullman, and Steven Wu. To appear in EC 2015.
  9. Private Pareto Optimal Exchange. Joint with Sampath Kannan, Jamie Morgenstern, and Ryan Rogers. To appear in EC 2015.
  10. Preserving Statistical Validity in Adaptive Data Analysis. Joint work with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, and Omer Reingold. To appear in STOC 2015.
  11. 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.
  12. Accuracy for Sale: Aggregating Data with a Variance Constraint. Joint with Rachel Cummings, Katrina Ligett, Steven Wu, and Juba Ziani. In the proceedings of ITCS 2015.
  13. 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.
  14. 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.
  15. Buying Private Data without Verification. Joint work with Arpita Ghosh, Katrina Ligett, and Grant Schoenebeck. In the proceedings of EC 2014.
  16. Asymptotically Truthful Equilibrium Selection in Large Congestion Games. Joint work with Ryan Rogers. In the proceedings of EC 2014.
  17. 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.
  18. Private Matchings and Allocations. Joint work with Justin Hsu, Zhiyi Huang, Tim Roughgarden, and Steven Wu. In the proceedings of STOC 2014.
  19. Mechanism Design in Large Games: Incentives and Privacy. Joint with Michael Kearns, Mallesh Pai, and Jon Ullman. In the proceedings of ITCS 2014.
  20. Constrained Signaling in Auction Design. Joint work with Shaddin Dughmi and Nicole Immorlica. In the proceedings of SODA 2014.
  21. Exploiting Metric Structure for Efficient Private Query Release. Joint work with Zhiyi Huang. In the proceedings of SODA 2014.
  22. Beyond Worst-Case Analysis in Private Singular Vector Computation. Joint with Moritz Hardt. In the proceedings of STOC 2013.
  23. Differential Privacy for the Analyst via Private Equilibrium Computation. Joint with Justin Hsu and Jon Ullman. In the proceedings of STOC 2013.
  24. Conducting Truthful Surveys, Cheaply. Joint with Grant Schoenebeck. In the proceedings of EC 2012.
  25. Beating Randomized Response on Incoherent Matrices. Joint with Moritz Hardt. In the proceedings of STOC 2012.
  26. 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.
  27. 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.
  28. New Algorithms for Preserving Differential Privacy. PhD Thesis.
  29. Interactive Privacy via the Median Mechanism. Joint with Tim Roughgarden. In the proceedings of STOC 2010.
  30. Constrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithms. Joint with Anupam Gupta, Grant Schoenebeck, and Kunal Talwar. In the Proceedings of WINE 2010.
  31. Differentially Private Combinatorial Optimization. Joint with Anupam Gupta, Katrina Ligett, Frank McSherry, and Kunal Talwar. In the Proceedings of  SODA 2010.
  32. Auctions with Online Supply. Joint with Moshe Babaioff and Liad Blumrosen. In the Proceedings Of EC 2010.
    Full version appears in Games and Economic Behavior, 2015.
  33. 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.
  34. 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)