Aaron Roth

Photo of me

About Me

I am the Raj and Neera Singh Assistant Professor of Computer and Information Science at the University of Pennsylvania computer science department, associated with the theory group and our new program in Market and Social Systems Engineering. 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.

If you are interested in joining a growing differential privacy group, consider applying to this postdoc in the theory and practice of differential privacy, this postdoc in the theory of privacy and economics, or applying to our PhD program in computer science. You might also consider attending our theory seminar.

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

Teaching

In the fall, I will be teaching a graduate course called The Algorithmic Foundations of Data Privacy. This will be a fun, project-based course designed to get anyone who takes it up to the research frontiers of differential privacy. It is a graduate course, but anyone with interest and sufficient mathematical maturity is encouraged to enroll.

In the spring, I will be teaching an undergraduate course in Algorithmic Game Theory. The course will cover modern topics on the interface between game theory and computer science, including efficient learning dynamics in zero-sum and general-sum games, the price of anarchy, and mechanism design in both classical settings and more modern settings (ad auctions, digital goods auctions, online auctions, mechanism design without money). We will review the basics of game theory, so no prior coursework in game theory is required. Students should have taken a course in algorithms, posess mathematical maturity, and be familiar with big-O notation.

Professional Activities

Program Committee Member For:
Selected Publications
 (See DBLP for a more complete list)
Click for abstract/informal discussion of results
  1. Distributed Private Heavy Hitters. Joint with Justin Hsu and Sanjeev Khanna. Manuscript.
  2. Take it or Leave it: Running a Survey when Privacy Comes at a Cost. Joint with Katrina Ligett. Manuscript.
  3. Beating Randomized Response on Incoherent Matrices. Joint with Moritz Hardt. To appear in the proceedings of STOC 2012.
  4. Fast Private Data Release Algorithms for Sparse Queries. Joint with Avrim Blum. Manuscript.
  5. Iterative Constructions and Private Data Release. Joint with Anupam Gupta and Jonathan Ullman. To appear in the proceedings of TCC 2012.
  6. Privately Releasing Conjunctions and the Statistical Query Barrier. Joint with Anupam Gupta, Moritz Hardt, and Jonathan Ullman. In the proceedings of STOC 2011.
  7. Selling Privacy at Auction. Joint work with Arpita Ghosh. In the proceedings of EC 2011, and invited to a special issue of Games and Economic Behavior.
  8. New Algorithms for Preserving Differential Privacy. PhD Thesis.
  9. Interactive Privacy via the Median Mechanism. Joint with Tim Roughgarden. In the proceedings of STOC 2010.
  10. Constrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithms. Joint with Anupam Gupta, Grant Schoenebeck, and Kunal Talwar. In the Proceedings of WINE 2010.
  11. Differentially Private Combinatorial Optimization. Joint with Anupam Gupta, Katrina Ligett, Frank McSherry, and Kunal Talwar. In the Proceedings of  SODA 2010.
  12. Auctions with Online Supply. Joint with Moshe Babaioff and Liad Blumrosen. In the Proceedings Of EC 2010.
  13. 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.
  14.  The Price of Stochastic Anarchy. Joint with Christine Chung, Katrina Ligett, and Kirk Pruhs. In the proceedings of SAGT 2008: The first Annual Symposium on Algorithmic Game Theory.
  15. 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)