Anna Karlin

University of Washington


Primary Section: 34, Computer and Information Sciences
Membership Type: Member (elected 2021)

Biosketch

Anna R. Karlin, is the Bill & Melinda Gates Chair and Professor of Computer Science and Engineering at the University of Washington. She received her Ph.D. in computer science from Stanford University in 1987. Before coming to the University of Washington, she spent 5 years as a researcher at (what was then) Digital Equipment Corporation's Systems Research Center. Her research is primarily in theoretical computer science: the design and analysis of algorithms, particularly algorithmic game theory, probabilistic, online and approximation algorithms. She is coauthor of the book “Game Theory, Alive” with Yuval Peres, published in 2017 by the American Mathematical Society. She is a Fellow of the Association for Computing Machinery, a co-winner of the 2021 Paris Kanellakis Theory and Practice Award, and a member of the American Academy of Arts and Sciences.

Research Interests

Anna Karlin’s research is in theoretical computer science, and specifically the design and analysis of algorithms. Her early work focused on the competitive analysis of online algorithms, in which decisions are made as each input arrives, without the benefit of information about future inputs, while still performing nearly as well as as a clairvoyant optimal decision maker. Another favorite topic throughout her career has been probabilistic algorithms and analysis. In the last decade, much of her research has been in algorithmic game theory, which addresses the question of how to merge algorithm design and optimization with strategic and game theoretic considerations. Applications of this theory range from network traffic routing and scheduling tasks in the cloud to ecommerce and search engine advertising. A final topic of recent interest is the quest to obtain algorithms that produce near-optimal solutions to NP-complete problems in polynomial time. An example of such a problem on which Karlin and her coauthors have made recent progress is the famous Travelling Salesperson Problem.

Powered by Blackbaud
nonprofit software