Katrina Ligett




Brief Bio

Katrina Ligett is an Associate Professor of Computer Science at Hebrew University, where she is also a member of the Federmann Center for the Study of Rationality. Her work is in algorithms, particularly in data privacy, algorithmic fairness, algorithmic game theory, and online algorithms. Her research is funded in part by the Israeli Science Foundation (ISF), the DARPA Brandeis project, and a grant from the Hebrew University Cyber Center.

Katrina received her PhD in summer 2009 from the Computer Science Department at Carnegie Mellon University, where her advisor was Avrim Blum. From fall 2009 through summer 2011, she was a postdoctoral fellow in Computer Science at Cornell University, hosted by √Čva Tardos and Bobby Kleinberg. She 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. From 2011-2017, Katrina was an Assistant Professor of Computer Science and Economics at Caltech.

Katrina has been affiliated with programs at the Simons Institute for Theoretical Computer Science at Berkeley, on Economics and Computation and on Algorithms and Uncertainty. She is co-organizing an upcoming program on Data Privacy.

Katrina has also in the past received generous funding through the NSF (including a CAREER award), the US-Israel Binational Science Foundation, a Google Faculty Research Award, an Okawa Foundation Research Grant, a Microsoft Research Faculty Fellowship, an AT&T Labs Graduate Research Fellowship, an NSF Graduate Research Fellowship, a CIFellows postdoctoral fellowship, and an NSF Mathematical Sciences Postdoctoral Fellowship.

Current Students: Yahav Bechavod, Aaron Koolyk, Miriam Manevitz, Moshe Shenfeld, Juba Ziani.

Past Students: Rachel Cummings (recipient of an ACM SIGecom Doctoral Dissertation Honorable Mention and the Caltech Amori Doctoral Prize in Computing and Mathematical Sciences)

Past Postdocs: Siddharth Barman, Georgios Piliouras, Yakov Babichenko, Umang Bhaskar.

Published/Forthcoming

Access to Population-Level Signaling as a Source of Inequality. With Nicole Immorlica and Juba Ziani. FAT* 2019.

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

Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM. With Seth Neel, Aaron Roth, Bo Waggoner, and Steven Wu. NIPS 2017. Also presented at TPDP 2017.

Commitment in First-price Auctions. With Yunjian Xu. Economic Theory. 2017.

Putting Peer Prediction Under the Micro(economic)scope and Making Truth-telling Focal. With Yuqing Kong and Grant Schoenebeck. Conference on Web and Internet Economics (WINE), 2016.

The Strange Case of Privacy in Equilibrium Models. With Rachel Cummings, Mallesh Pai, and Aaron Roth. Economics and Computation (EC), 2016.

Adaptive Learning with Robust Generalization Guarantees. With Rachel Cummings, Kobbi Nissim, Aaron Roth, and Zhiwei Steven Wu. Conference on Learning Theory (COLT), 2016.

Coordination Complexity: Small Information Coordinating Large Populations. With Rachel Cummings, Jaikumar Radhakrishnan, Aaron Roth, and Zhiwei Steven Wu. Innovations in Theoretical Computer Science (ITCS), 2016.

Commitment in First-Price Auctions. With Yunjian Xu. SAGT 2015.

Approximating Nash Equilibria in Tree Polymatrix Games. With Siddharth Barman and Georgios Piliouras. SAGT 2015.

Finding any Nontrivial Coarse Correlated Equilibrium is Hard. With Siddharth Barman. EC 2015.

Truthful Linear Regression. With Rachel Cummings and Stratis Ioannidis. COLT 2015.

Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard. With Siddharth Barman. SIGecom Exchanges, Volume 14, Number 1, 2015.

Network Improvement for Equilibrium Routing. With Umang Bhaskar. SIGecom Exchanges, Volume 13, Number 2, 2014.

Accuracy for Sale: Aggregating Data with a Variance Constraint. With Rachel Cummings, Aaron Roth, Zhiwei Steven Wu and Juba Ziani. ITCS 2015.

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

February 12-16, 2017: 7th BIU Winter School on Cryptography. Differential Privacy: From Theory to Practice.

December 8, 2014: Differential Privacy and Learning: The Tools, The Results, and The Frontier, Neural and Information Processing Systems (NIPS) invited tutorial.

December 11, 2013: Tutorial on Differential Privacy, Simons Institute Workshop on Big Data and Differential Privacy, Berkeley.




Katrina Ligett