Katrina Ligett

Home      Research      Teaching      Service

I work in algorithms, particularly online algorithms, algorithmic game theory, and data privacy.

My advisor is Avrim Blum. From 2004 to 2007 I was supported in part by an AT&T Labs Graduate Research Fellowship. My mentor at AT&T is David S. Johnson. I am currently supported in part by an NSF Graduate Research Fellowship.

Recent Publications

A Learning Theory Approach to Non-Interactive Database Privacy. With Avrim Blum and Aaron Roth. STOC 2008.

Regret Minimization and the Price of Total Anarchy. With Avrim Blum, MohammadTaghi Hajiaghayi, and Aaron Roth. STOC 2008.

The Price of Stochastic Anarchy. With Christine Chung, Kirk Pruhs, and Aaron Roth. SAGT 2008 (First International Symposium on Algorithmic Game Theory).

Playing Games with Approximation Algorithms. With Sham Kakade and Adam Tauman Kalai. STOC 2007. Journal version in submission.

Compressing Rectilinear Pictures and Minimizing Access Control Lists. With David A. Applegate, Gruia Calinescu, David S. Johnson, Howard Karloff, and Jia Wang. SODA 2007.

Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games. With Avrim Blum and Eyal Even-Dar. PODC 2006. Journal version in submission.

Talks

  • September 25, 2008: "A Learning Theory Approach to Non-Interactive Database Privacy," China Theory Week 2008, Institute for Theoretical Computer Science, Tsinghua University.

  • September 8, 2008: "A Learning Theory Approach to Non-Interactive Database Privacy," Cornell Theory Seminar.

  • August 18, 2008: "Rational Expectations in Games; Robust Statistics and Streaming," Microsoft Research Silicon Valley.

  • May 19, 2008: "Regret Minimization and the Price of Total Anarchy," Symposium on Theory of Computing (STOC).

  • May 7, 2008: "Regret Minimization and the Price of Total Anarchy," Max Planck Institut fuer Informatik, Saarbruecken.

  • April 30, 2008: "Bertrand Competition in Networks," Symposium on Algorithmic Game Theory. Talk given on behalf of Shuchi Chawla and Tim Roughgarden.

  • February 13, 2008: "A Learning Theory Approach to Non-Interactive Database Privacy," CMU Theory Lunch.

  • February 5, 2008: "A Learning Theory Approach to Non-Interactive Database Privacy," DIMACS Workshop on Data Privacy.

  • December 11, 2007: "Approximate Online Linear Optimization," Penn State.

  • June 28, 2007: "Self-Interested Players in Repeated Games: Minimizing Regret," Dagstuhl Workshop on Fair Division.

  • June 13, 2007: "Playing Games with Approximation Algorithms," Symposium on Theory of Computing (STOC).

  • January 9, 2007: "Compressing Rectilinear Pictures and Minimizing Access Control Lists," Symposium on Discrete Algorithms (SODA).

  • December 13, 2006: "Approximate Online Linear Optimization," CMU Theory Lunch.

  • November 8, 2006: "Approximate Online Linear Optimization," INFORMS Annual Meeting.

  • July 24, 2006: "Routing Without Regret," Symposium on Principles of Distributed Computing.

  • May 10, 2006: "Truthful, Near-Optimal Mechanism Design," CMU Theory Lunch.

  • May 8, 2006: "Routing Without Regret," Electronic Marketplaces workshop, Carnegie Mellon University.

  • November 13, 2005: "Routing Without Regret," INFORMS Annual Meeting.

  • May 4, 2005: "Routing Without Regret," CMU Theory Lunch.

Home      Research      Teaching      Service

Katrina Ligett