Anna R. Karlin

Microsoft Professor of Computer Science & Engineering
Allen School of Computer Science & Engineering
Box 352350
PGA 594
University of Washington
Seattle, WA 98195-2350

(206) 543-9344 voice
(206) 543-2969 FAX

karlin at cs dot washington dot edu

Selected Publications
Current Students
Recent Teaching
Short Bio

I'm general chair for the 20th ACM Conference on Economics and Computation, which will held in Phoenix, AZ from June 24-28 as part of FCRC'19.

Why Women (and Everyone Else) Should Code

Game Theory, Alive with Y. Peres

The book can be purchased at the American Mathematical Society Bookstore or at

Selected Publications

Research currently supported by NSF grant CCF-1813135

  • A simply exponential upper bound on the maximum number of stable matchings (with S. Oveis Gharan and R. Weber)

  • Stability of service under time-of-use pricing (with S. Chawla, N. Devanur, A. Holroyd, J. Martin, B. Sivan).

  • The FedEx Problem (with A. Fiat, K. Goldner and E. Koutsoupias).

  • A prior-independent revenue-maximizing auction for multiple additive bidders (with K. Goldner)

  • Carpooling in a social network (with A. Fiat, E. Koutsoupias, C. Mathieu and R. Zach).

  • Simple pricing schemes for consumers with evolving data (with S. Chawla, N. Devanur and B. Sivan).

  • Approximate revenue maximization in interdependent value settings (with S. Chawla and H. Fu).

  • Prior-independent multi-parameter mechanism design (with N. Devanur, J. Hartline and T. Nguyen)

  • Greedy Bidding Strategies for Keyword Auctions (with M. Cary, A. Das, B. Edelman, I. Giotis, K. Heimerl, C. Mathieu and M. Schwarz)

  • Cheap Labor Can Be Expensive (with N. Chen)

  • Beyond VCG: Frugality in Truthful Mechanisms (with D. Kempe and T. Tamir)

  • On profit-maximizing envy-free pricing (with V. Guruswami, J. Hartline, D. Kempe, C. Kenyon and F. McSherry)

  • Truthful and competitive double auctions (with K. Deshmukh, A. Goldberg and J. Hartline)

  • Competitive generalized auctions (with A. Fiat, A. Goldberg and J. Hartline)

  • Competitive auctions (with A. Goldberg, J. Hartline, M. Saks and A. Wright)

  • Web search via hub Synthesis (with D. Achlioptas, A. Fiat and F. McSherry)

  • Spectral analysis for data mining (with Y. Azar, A. Fiat, F. McSherry and J. Saia)

  • On algorithms for efficient data migration (with J. Hall, J. Hartline, J. Saia and J. Wilkes)

  • Random walks with back buttons (with R. Fagin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan and A. Tomkins)

  • Practical Network Support for IP Traceback. (with S. Savage, D. Wetherall and T. Anderson).

  • Web Tracing and Web Caching Project and Papers

  • On List Update and Work Function Algorithms (with E. Anderson, K. Hildrum, A. Rasala and M. Saks)

  • Implementing Global Memory Management in a Workstation Cluster. (with Michael J. Feeley, William E. Morgan, Frederic H. Pighin, Henry M. Levy, and Chandramohan A. Thekkath.)

  • Two Adaptive Hybrid Cache Coherencey Protocols (with C. Anderson)

  • Implementation and Performance of Integrated Application-Controlled Caching, Prefetching and Disk Scheduling (with P. Cao, E. Felten and K. Li)

  • Reducing TLB and Memory Overhead Using Online Superpage Promotion (with T. Romer, W. Ohlrich and B. Bershad)

  • A Study of Integrated Prefetching and Caching Strategies (with P. Cao, E. Felten and K. Li)

  • Randomized and Multipointer Paging with Locality of Reference (with A. Fiat)

  • Balanced Allocations (with Y. Azar, A. Broder and E. Upfal)

  • On the Fault Tolerance of the Butterfly (with G. Nelson and H. Tamaki)

  • Markov Paging (with S. Phillips and P. Raghavan)

  • Strongly Competitive Algorithms for Paging with Locality of Reference (with S. Irani and S. Phillips)

  • An Empirical Study of Competitive Spinning for a Shared-Memory Multiprocessor (with K. Li, M. Manasse and S. Owicki )

  • Trading Space for Time in Undirected s-t Connectivity (with A. Broder, P. Raghavan and E. Upfal )

    Current Students

  • Kira Goldner

  • Nathan Klein

  • Robbie Weber

    Former Students (in order of graduation)

  • Juan Alemany

  • Eric Anderson

  • Jason Hartline

  • Tracy Kimbrel

  • Frank McSherry

  • Jared Saia

  • Matt Cary

  • Ning Chen

  • Ioannis Giotis

  • Cam Thach Nguyen

  • Ben Birnbaum

  • Elisa Celis

  • Jessica Chang

    Recent Teaching (very partial list)

  • Algorithms and Uncertainty, cotaught with Nikhil Devanur.

  • Over the last few years, I have created and taught a new course to non-computer science students in the Honors College at the University of Washington: A Brave New World: The Scientific, Economic and Social Impact of Computer Science. (Thanks to Google for support.)

  • CSE 525: Randomized Algorithms

    Short Bio

    Anna Karlin, Microsoft Professor of Computer Science and Engineering, received her Ph.D. 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 probabilistic and online algorithms. She also works at the interface between theory and other areas, such as economics and game theory, data mining, operating systems, networks, and distributed systems.

    "The computer is useless. It can only answer questions."
                                                     Pablo Picasso

    "When my brothers try to draw a circle to exclude me, I shall draw a larger circle to include them.."
                                                     Pauli Murray