Aaron Roth


About Me

 I am a third year PhD student at Carnegie Mellon. My advisor is Avrim Blum, and my main interests are in algorithms and game theory. Most of my work relates to computing under semantic restrictions in addition to computational restrictions. What is achievable when elements of a system are self interested? What can be computed while preserving the privacy of the input?

Prior to CMU, I attended Columbia University where I got a BA in mathematics and computer science. I am fortunate to be supported by an NSF graduate fellowship. I've enjoyed spending some time at Microsoft Research. My lovely fiance Cathy is getting her PhD in math at MIT. At her insistence, I link to her website

Contact Information

You can find me in my Wean Hall office room 8112, or email me at: alr...@cs.cmu.edu. (To discover my email address either solve a ReCaptcha, or apply careful deductive logic to the URL of this page).

Publications
Click for abstract/informal discussion of results

  1. On the Equilibria of Asynchronous Games. Joint with Nina Balcan, Adam Kalai, and Yishay Mansour. In Submission.
  2. Differentially Private Approximation Algorithms. Joint with Anupam Gupta, Katrina Ligett, Frank McSherry, and Kunal Talwar. In Submission.
  3. Auctions with Online Supply. Joint with Moshe Babaioff and Liad Blumrosen. In Submission.
  4. The Price of Malice in Linear Congestion Games. In the proceedings of WINE 2008: The fourth International Workshop on Internet and Network Economics.
  5. 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.
  6. 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.
  7. 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

Misc

I no longer organize theory lunch, but you should still give a talk there. I (sometimes) maintain a blog