Katrina Ligett




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

My work is funded in part by an NSF CAREER award, a Microsoft Research Faculty Fellowship, the US-Israel Binational Science Foundation, an NSF award through the United States-Israel Collaboration in Computer Science, and a Google Faculty Research Award. I have also in the past received generous funding through an AT&T Labs Graduate Research Fellowship, an NSF Graduate Research Fellowship, a CIFellows postdoctoral fellowship, and an NSF Mathematical Sciences Postdoctoral Fellowship.

At Caltech, I am involved in the Center for the Mathematics of Information (CMI), Social and Information Sciences Lab (SISL), and the Rigorous Systems Research Group (RSRG).

I received my PhD in summer 2009 from the Computer Science Department at Carnegie Mellon University, where my advisor was Avrim Blum. From fall 2009 through summer 2011 I was a postdoctoral fellow in Computer Science at Cornell University, hosted by √Čva Tardos and Bobby Kleinberg. I spent spring 2011 as a visitor at the Research Group on Algorithmic Game Theory at the Rationality Center and Institute for Advanced Studies at Hebrew University in Jerusalem.

Postdocs: Yakov Babichenko, Siddharth Barman, Umang Bhaskar, Georgios Piliouras.
Students: Rachel Cummings, Juba Ziani.

Published/Forthcoming

Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions. With Umang Bhaskar, Leonard Schulman, and Chaitanya Swamy. FOCS, 2014.

Privacy and Data-Based Research. With Ori Heffetz. Journal of Economic Perspectives, 2014. [JEP version] [SSRN version] [NBER Working Paper No. w19433]

Buying Private Data without Verification. With Arpita Ghosh, Aaron Roth, and Grant Schoenebeck. EC, 2014.

Network Improvement for Equilibrium Routing. With Umang Bhaskar and Leonard J. Schulman. IPCO, 2014.

Beyond Myopic Best Response (in Cournot Competition). With Amos Fiat, Elias Koutsoupias, Yishay Mansour, and Svetlana Olonetsky. Games and Economic Behavior, 2014. Conference version linked below.

Information-Sharing in Social Networks. With Jon Kleinberg. Games and Economic Behavior, 2013.

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

A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret. With Lachlan L.H. Andrew, Siddharth Barman, Minghong Lin, Adam Meyerson, Alan Roytman, and Adam Wierman. COLT 2013.

Privacy and Coordination: Computing on Databases with Endogenous Participation. With Arpita Ghosh. EC 2013.

Improved Bounds on the Price of Stability in Network Cost Sharing Games. With Euiwoong Lee. EC 2013.

Privacy as a Coordination Game. With Arpita Ghosh. Allerton 2013.

A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret. With Lachlan L.H. Andrew, Siddharth Barman, Minghong Lin, Adam Meyerson, Alan Roytman, and Adam Wierman. ACM Sigmetrics, 2013 (poster; conference version appeared at COLT 2013).

Contention Resolution under Selfishness. With George Christodoulou and Evangelia Pyrga. Algorithmica, 2013.

Take it or Leave it: Running a Survey when Privacy Comes at a Cost. With Aaron Roth. WINE 2012.

A Simple and Practical Algorithm for Differential Privacy. With Moritz Hardt and Frank McSherry. NIPS 2012.

Beyond Myopic Best Response (in Cournot Competition). With Amos Fiat, Elias Koutsoupias, Yishay Mansour, and Svetlana Olonetsky. SODA 2012. Journal version above.

Beating the Best Nash Without Regret. With Georgios Piliouras. SIGecom Exchanges, Vol. 10, No. 1, March 2011.

Beyond the Nash Equilibrium Barrier. With Robert Kleinberg, Georgios Piliouras, and Eva Tardos. ICS 2011.

The Power of Fair Pricing Mechanisms. With Christine Chung, Kirk Pruhs, and Aaron Roth. Algorithmica 2011.

Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games. With Avrim Blum and Eyal Even-Dar. Theory of Computing, Volume 6, 2010.

Privacy-Compatibility For General Utility Metrics. With Robert Kleinberg. (manuscript)

Contention Resolution under Selfishness. With George Christodoulou and Evangelia Pyrga. ICALP 2010. Journal version above.

The Power of Fair Pricing Mechanisms. With Christine Chung, Kirk Pruhs, and Aaron Roth. LATIN 2010. Journal version above.

Space-Efficient Estimation of Robust Statistics and Distribution Testing. With Steve Chien and Andrew McGregor. Innovations in Computer Science (ICS) 2010.

Differentially Private Approximation Algorithms. With Anupam Gupta, Frank McSherry, Aaron Roth, and Kunal Talwar. SODA 2010.

Playing Games with Approximation Algorithms. With Sham Kakade and Adam Tauman Kalai. SIAM Journal on Computing (SICOMP) 2009, special issue for STOC 2007.

On the Price of Stability for Undirected Network Design. With Christine Chung, George Christodoulou, Evangelia Pyrga and Rob van Stee. Workshop on Approximation and Online Algorithms (WAOA) 2009 .

Differential Privacy with Compression. With Shuheng Zhou and Larry Wasserman. International Symposium on Information Theory (ISIT) 2009.

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. Symposium on Algorithmic Game Theory (SAGT) 2008.

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

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 linked above.

Tutorials

Talks




Katrina Ligett