Katrina Ligett

Home      Research      Teaching      Service

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.

My research interests lie in the area of algorithms, particularly online algorithms and algorithmic game theory. My favorite problems are simple to explain, elegant, and universal (show up in many places in different forms).

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

  • 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