Anna R. Karlin

Bill and Melinda Gates Chair in 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 Papers
Current Students
Some Teaching
Short Bio

Game Theory, Alive with Y. Peres

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


Selected Papers

  • A (slightly) improved approximation algorithm for metric TSP (with N. Klein and S. Oveis Gharan)

  • An improved approximation algorithm for TSP in the half integral case (with N. Klein and S. Oveis Gharan)

  • Combinatorial auctions with interdependent valuations: SOS to the rescue (with A. Eden, M. Feldman, A. Fiat and K. Goldner)

  • 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

  • Nathan Klein (jointly advised with Shayan Oveis Gharan)

  • Xinzhi Zhang (jointly advised with Shayan Oveis Gharan)

    Former Students (in order of graduation)

  • Juan Alemany

  • Eric Anderson

  • Jason Hartline

  • Tracy Kimbrel (jointly adviced with Martin Tompa)

  • Frank McSherry

  • Jared Saia

  • Matt Cary

  • Ning Chen

  • Ioannis Giotis

  • Cam Thach Nguyen

  • Ben Birnbaum (jointly advised with Gaetano Borriello)

  • Elisa Celis (jointly advised with Yuval Peres)

  • Jessica Chang

  • Kira Goldner

  • Robbie Weber (jointly advised with Shayan Oveis Gharan)

    Some of my 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, the Bill and Melinda Gates Chair in 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.


    Some quotes

    The real problem of humanity is the following: We have Paleolithic emotions, medieval institutions and godlike technology.
                                                     Edward O. Wilson

    When everyone says the same thing about some complex topic, what should come to your mind is, wait a minute, nothing can be that simple. Something’s wrong. That’s the immediate light that should go off in your brain when you ever hear unanimity on some complex topic.
                                                     Noam Chomsky

    People wish to be settled; only in so far as they are unsettled is there any hope for them.
                                                     Ralph Waldo Emerson

    Do not fear to be eccentric in opinion, for every opinion now accepted was once eccentric.
                                                     Bertrand Russell

    Fight for the things that you care about, but do it in a way that will lead others to join you.
                                                     Ruth Bader Ginsburg

    When a thoughtless or unkind word is spoken, best tune out. Reacting in anger or annoyance will not advance one's ability to persuade.
                                                     Ruth Bader Ginsburg

    Nonviolence is a powerful and just weapon which cuts without wounding and ennobles the man who wields it. It is a sword that heals.
    Violence as a way of achieving racial justice is both impractical and immoral.
                                                     Martin Luther King Jr.

    Humility is not thinking less of yourself, it's thinking of yourself less.
                                                     C.S. Lewis

    What is it you wanted me to reconcile myself to? I was born here, almost 60 years ago. I'm not going to live another 60 years. You always told me `It takes time.' It's taken my father's time, my mother's time, my uncle's time, my brothers' and my sisters' time. How much time do you want for your progress?
                                                     James Baldwin

    First they came for the socialists, and I did not speak out, because I was not a socialist.
    Then they came for the trade unionists, and I did not speak out, because I was not a trade unionist.
    Then they came for the Jews, and I did not speak out, because I was not a Jew.
    Then they came for me -- and there was no one left to speak for me.
                                                     Martin Niemöller

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

    I don’t think that meaningful constructive social change can take place unless the large majority of the population have come to the realization that modifications of existing systems cannot achieve the kinds of goals that they think are right and just. At that point, you can have radical social change. If it’s forced prior to that, I think it ends up in some kind of authoritarian structure again.
                                                     Noam Chomsky

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