Katrina Ligett

Last updated
Katrina Ligett
Nationality American
Alma mater Carnegie Mellon University
Known for Algorithmic game theory, privacy
Scientific career
Fields Computer Science
Institutions Hebrew University
Doctoral advisor Avrim Blum

Katrina Ligett is an American computer scientist. She is Associate Professor of computer science and economics at the Hebrew University and Visiting Associate at California Institute of Technology. She is known for work on algorithmic game theory and privacy.

Contents

Education

Ligett studied at Brown University, where she completed her BS degree in Mathematics and Computer Science in 2004. She then earned her MS and PhD in Computer Science from Carnegie Mellon University in 2007 and 2009, respectively. Her PhD was supervised by Avrim Blum. [1] She has been on the faculty of the California Institute of Technology since 2011. [2] Currently she is Associate Professor of Computer Science and Member of Federmann Center for the Study of Rationality at Hebrew University, as well as Visiting Associate in Computing and Mathematical Sciences at Caltech.

Research

Ligett's work has made notable contributions to two fields: privacy and algorithmic game theory. For example, in the field of data privacy, her work provided a foundation for the field by proving the possibility of answering exponentially many queries about a database while maintaining privacy for individuals. [3] In the field of algorithmic game theory, her work showed that efficiency guarantees proven for Nash equilibrium (so called Price of Anarchy bounds) can be extended to weaker equilibria concepts. [4]

Awards and honors

Ligett received a Microsoft Faculty Research Fellowship in 2013. [1] In the same year, she received an NSF CAREER award and a Google Faculty Research Award [5]

Related Research Articles

<span class="mw-page-title-main">Ron Rivest</span> American cryptographer

Ronald Linn Rivest is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). His work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity.

<span class="mw-page-title-main">John Hopcroft</span> American computer scientist (born 1939)

John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University, Co-Director of the Center on Frontiers of Computing Studies at Peking University, and the Director of the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University.

<span class="mw-page-title-main">Manuel Blum</span> Venezuelan computer scientist

Manuel Blum is a Venezuelan-American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".

<span class="mw-page-title-main">Shafi Goldwasser</span> American computer scientist

Shafrira Goldwasser is an Israeli-American computer scientist and winner of the Turing Award in 2012. She is the RSA Professor of Electrical Engineering and Computer Science at MIT, a professor of mathematical sciences at the Weizmann Institute of Science, Israel, co-founder and chief scientist of Duality Technologies and the director of the Simons Institute for the Theory of Computing at the University of California, Berkeley.

<span class="mw-page-title-main">Lenore Blum</span> American computer scientist and mathematician

Lenore Carol Blum is an American computer scientist and mathematician who has made pioneering contributions to the theories of real number computation, cryptography, and pseudorandom number generation. She was a distinguished career professor of computer science at Carnegie Mellon University until 2019 and is currently a professor in residence at the University of California, Berkeley. She is also known for her efforts to increase diversity in mathematics and computer science.

<span class="mw-page-title-main">Ravindran Kannan</span>

Ravindran Kannan is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science.

<span class="mw-page-title-main">Jeannette Wing</span> American computer scientist

Jeannette Marie Wing is Avanessians Director of the Data Science Institute at Columbia University, where she is also a professor of computer science. Until June 30, 2017, she was Corporate Vice President of Microsoft Research with oversight of its core research laboratories around the world and Microsoft Research Connections. Prior to 2013, she was the President's Professor of Computer Science at Carnegie Mellon University, Pittsburgh, Pennsylvania, United States. She also served as assistant director for Computer and Information Science and Engineering at the NSF from 2007 to 2010. She was appointed the Columbia University executive vice president for research in 2021.

<span class="mw-page-title-main">Avrim Blum</span> American computer scientist

Avrim Blum is a computer scientist. In 2007, he was made a Fellow of the Association for Computing Machinery "for contributions to learning theory and algorithms." Blum attended MIT, where he received his Ph.D. in 1991 under professor Ron Rivest. He was a professor of computer science at Carnegie Mellon University from 1991 to 2017.

Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.

<span class="mw-page-title-main">Cynthia Dwork</span> American computer scientist

Cynthia Dwork is an American computer scientist best known for her contributions to cryptography, distributed computing, and algorithmic fairness. She is one of the inventors of differential privacy and proof-of-work.

Differential privacy (DP) is a system for publicly sharing information about a dataset by describing the patterns of groups within the dataset while withholding information about individuals in the dataset. The idea behind differential privacy is that if the effect of making an arbitrary single substitution in the database is small enough, the query result cannot be used to infer much about any single individual, and therefore provides privacy.

<span class="mw-page-title-main">Toniann Pitassi</span> Canadian-American computer scientist

Toniann Pitassi is a Canadian-American mathematician and computer scientist specializing in computational complexity theory. She is currently Jeffrey L. and Brenda Bleustein Professor of Engineering at Columbia University and was Bell Research Chair at the University of Toronto.

<span class="mw-page-title-main">Noam Nisan</span> Israeli computer scientist

Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.

Shuchi Chawla is an Indian computer scientist who works in the design and analysis of algorithms, and is known for her research on correlation clustering, information privacy, mechanism design, approximation algorithms, hardness of approximation, and algorithmic bias. She works as a professor of computer science at the University of Texas at Austin.

<span class="mw-page-title-main">Yael Tauman Kalai</span> Cryptographer and theoretical computer scientist

Yael Tauman Kalai is a cryptographer and theoretical computer scientist who works as a Senior Principal Researcher at Microsoft Research New England and as an adjunct professor at MIT in the Computer Science and Artificial Intelligence Lab.

<span class="mw-page-title-main">Adam Tauman Kalai</span> American computer scientist

Adam Tauman Kalai is an American computer scientist who specializes in Machine Learning and works as a Senior Principal Researcher at Microsoft Research New England.

<span class="mw-page-title-main">Michal Feldman</span> Israeli computer scientist

Michal Feldman is a full professor of Computer Science and the Chair of Computation and Economics at Tel Aviv University, the head of Economics and Computation (EC) lab, and a visiting researcher in Microsoft Research Israel. Michal’s research focuses on algorithmic game theory, an area that lies in the intersection of computer science, microeconomics and game theory. Among other topics, she studies auction theory, mechanism design, algorithm design, the price of anarchy, and e-commerce. Michal is an alumna of the Israel Young Academy and of the Global Young Academy. Her research is funded by prestigious grants, including, among others, grants of the ERC : ERC starters and ERC consolidator, ISF grants, and an Amazon Research Award. She was selected by the Forbes magazine as one of the most influencing women in Israel in 2016., and was recently awarded the Kadar Award for Outstanding Research.

Maria-Florina (Nina) Balcan is a Romanian-American computer scientist whose research investigates machine learning, algorithmic game theory, theoretical computer science, including active learning, kernel methods, random-sampling mechanisms and envy-free pricing. She is an associate professor of computer science at Carnegie Mellon University.

Aaron Roth is an American computer scientist. He is the Henry Salvatori Professor of Computer and Cognitive Science at the University of Pennsylvania.

References

  1. 1 2 Microsoft Research Faculty Fellows 2013
  2. Katrina Ligett at the Caltech Directory
  3. Blum, Avrim; Ligett, Katrina; Roth, Aaron (2008), A learning theory approach to noninteractive database privacy, p. 609, arXiv: 1109.2229 , doi:10.1145/1374376.1374464, ISBN   9781605580470, S2CID   53039307
  4. Blum, Avrim; Hajiaghayi, Mohammadtaghi; Ligett, Katrina; Roth, Aaron (2008), "Regret minimization and the price of total anarchy", Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08, p. 373, CiteSeerX   10.1.1.116.5105 , doi:10.1145/1374376.1374430, ISBN   9781605580470, S2CID   12589969
  5. Google Faculty Research Award Recipients