Katrina Ligett
Brief Bio
Katrina Ligett is a Professor of Computer Science at the Hebrew University, where she is also the director 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 currently funded in part by the Israeli Science Foundation (ISF), a Simons Foundation Collaboration grant, the Israeli Council for Higher Education, and a gift to the McCourt School of Public Policy at Georgetown University.
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 co-organized a Simons Institute program on
Data Privacy in Spring 2019.
From July 2022 to February 2023, Katrina was the Microsoft Visiting Professor at Princeton University's Center for Information Technology Policy.
Katrina has also in the past received generous funding through the ISF, DARPA/US Air Force, the DARPA Brandeis project, a grant from the Hebrew University Cyber Center, the NSF (including a CAREER award),
the US-Israel Binational Science Foundation,
Google Faculty Research Awards, 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: Etam Benger, Moshe Shenfeld, Tomer Shoham (co-advised with Yosef Rinott).
Current Postdocs: Ayelet Gordon, Tomer Shadmy.
Graduated MSc Students: Hadas Gross, Yehonatan Mizrahi (co-advised with Liad Blumrosen), Moshe Shenfeld, Yahav Bechavod, Miriam Manevitz.
Graduated PhD Students: Juba Ziani (recipient of the Bhansali Family Doctoral Prize in Computer Science at Caltech),
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
Reimagining Decentralized AI. With Tomer Shadmy. ACM CSLaw 2024.
Generalization in the Face of Adaptivity: A Bayesian Perspective.
With Moshe Shenfeld. NeurIPS 2023.
The Privacy Elasticity of Behavior: Conceptualization and Application. With Inbal Dekel, Rachel Cummings, and Ori Heffetz. EC 2023.
We Need to Focus on How Our Data Is Used, Not Just How It Is Shared.
With Kobbi Nissim. CACM 2023.
The case for establishing a collective perspective to address the harms of platform personalization.
With Ayelet Gordon-Tapiero and Alexandra Wood. Vanderbilt Journal of Entertainment and Technology Law, 2023. Conference version appeared at ACM CSLaw 2022.
Gaming Helps! Learning from Strategic Interactions in Natural Dynamics.
With Yahav Bechavod, Steven Wu, and Juba Ziani. AISTATS, 2021.
Learn to Expect the Unexpected: Probably Approximately Correct Domain Generalization.
With Vikas K Garg, Adam Tauman Kalai, and Steven Wu. AISTATS, 2021.
Privately Learning Thresholds: Closing the Exponential Gap.
With Haim Kaplan, Yishay Mansour, Moni Naor, Uri Stemmer.
COLT, 2020.
Third-Party Data Providers Ruin Simple Mechanisms.
With Yang Cai, Federico Echenique, Hu Fu, Adam Wierman, and Juba Ziani.
SIGMETRICS, 2020.
Bounded-Leakage Differential Privacy.
With Charlotte Peale and Omer Reingold.
FORC (Foundations of Responsible Computing), 2020.
A New Analysis of Differential Privacy's Generalization Guarantees. With Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld.
ITCS 2020.
Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM. With Seth Neel, Aaron Roth, Bo Waggoner, and Steven Wu. Journal of Privacy and Confidentiality 9(2), 2019. See conference version below.
A Necessary and Sufficient Stability Notion for Adaptive Generalization. With Moshe Shenfeld. NeurIPS 2019.
Equal Opportunity in Online Classification with Partial Feedback. With Yahav Bechavod, Aaron Roth, Bo Waggoner, and Steven Wu. NeurIPS 2019.
Learning to Prune: Speeding up Repeated Computations. With
Daniel Alabi, Adam Tauman Kalai, Cameron Musco, Christos Tzamos, and Ellen Vitercik. COLT 2019.
Access to Population-Level Signaling as a Source of
Inequality. With Nicole Immorlica and Juba Ziani. FAT* 2019.
Beyond Myopic Best Response (in Cournot Competition). With Amos Fiat, Elias Koutsoupias, Yishay Mansour, and Svetlana Olonetsky. Games and Economic Behavior, 2019. Conference version linked below.
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. See journal version above.
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.
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
June 23-27, 2024: Jerusalem Summer School in Economics. Computer Science and Economic Theory.
January 18-21, 2021: XVI Latin American Summer School in Discrete Mathematics. Differential Privacy.
January 31-February 1, 2019: Data Privacy: Foundations and Applications Boot Camp at the Simons Institute. Markets and Incentives for Transacting on (Personal) Information.
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.
Keynotes
Federated and Collaborative Learning Workshop, Simons Institute, 2023.
Theory and Practice of Differential Privacy Workshop (TPDP), 2021.
ACM Conference on Fairness, Accountability, and Transparency (FAccT), 2021.
PriML/PPML Workshop on Privacy-Preserving Machine Learning at NeurIPS, 2020.
Katrina Ligett