About Me

 I am a PhD student at Carnegie Mellon. My advisor is Avrim Blum, and my main interests are in algorithms and theoretical computer science. Most of my work relates to computing under interesting formalizations of social constraints, in addition to computational constraints. What is achievable when elements of a system are self interested? What can be computed when it is important to preserve the privacy of the users which make up the problem instance?

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 office in the Gates Center, room 7217, 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. The Median Mechanism: Interactive and Efficient Privacy with Multiple Queries. Joint with Tim Roughgarden. In Submission.
2. Constrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithms. Joint with Anupam Gupta, Grant Schoenebeck, and Kunal Talwar. In Submission.
3. On the Equilibria of Alternating Move Games. Joint with Nina Balcan, Adam Kalai, and Yishay Mansour. To Appear in SODA 2010
   
4. Differentially Private Combinatorial Optimization. Joint with Anupam Gupta, Katrina Ligett, Frank McSherry, and Kunal Talwar. To Appear in SODA 2010
   
5. Auctions with Online Supply. Joint with Moshe Babaioff and Liad Blumrosen. In Submission. Presented at the Fifth Workshop on Ad Auctions, 2009.
   
6. The Price of Malice in Linear Congestion Games. In the proceedings of WINE 2008: The fourth International Workshop on Internet and Network Economics.
7. 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.
8. 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.
9. 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

• On the Equilibria of Asynchronous Games (Slides)
• Microsoft Research SVC
• CMU Theory Lunch
• China Theory Week 2009
• Differentially Private Approximation Algorithms (Slides)
• Microsoft Research New England
• CMU Theory Lunch
• Princeton Theory Lunch
• Auctions with Online Supply (Slides)
• CMU Theory Lunch
• Microsoft Research SVC
• A Learning Theory Approach to Non-Interactive Database Privacy (Slides)
• Microsoft Live Labs Tech Talk
• STOC 2008
• Capital Area Theory Seminar (University of Maryland)
• CMU/Microsoft Privacy Mindswap (Poster)
• Regret Minimization and the Price of Total Anarchy (Slides)
• CMU Theory lunch
• GAMES 2008: 3rd World Congress of the Game Theory Society
• Harvard EconCS seminar
• ISMP 2009
  

Misc

I am the graduate student ombudsman for the computer science department. I no longer organize theory lunch, but you should still give a talk there. I (sometimes) maintain a blog.