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

Game Theory Book
Selected Publications
Current Students
Recent Teaching
Short Bio

ITCS 2018

I am chairing the 2018 ITCS (Innovations in Theoretical Computer Science) conference, which will be held January 11-14, 2018 at MIT.

Here is the list of accepted papers.

ITCS seeks to promote research that carries a strong conceptual message (e.g., introducing a new concept, model or understanding, opening a new line of inquiry within traditional or interdisciplinary areas, introducing new mathematical techniques and methodologies, or new applications of known techniques). ITCS welcomes all submissions, whether aligned with current theory of computation research directions or deviating from them. The PC will work hard to choose a set of papers that make a conceptually significant technical contribution and whose contents will educate and inspire the greater theory community.

Please join us at the conference!


New Game Theory Book!

Game Theory, Alive with Yuval Peres

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


Selected Publications

Research supported by NSF grant CCF-1016509

  • 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

  • Jiechen Chen

  • Kira Goldner

  • 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