Anna R. Karlin

Microsoft Professor of Computer Science & Engineering
Department 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
Short Bio

Selected Publications

  • 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

  • Ben Birnbaum

  • Elisa Celis

  • Jessica Chang

  • Ioannis Giotis

  • Cam Thach Nguyen

    Former Students (in order of graduation)

  • Juan Alemany

  • Eric Anderson

  • Jason Hartline

  • Tracy Kimbrel

  • Frank McSherry

  • Jared Saia

  • Matt Cary

  • Ning Chen

    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.

    Outside of work, she is delighted to have her time is taken up by her daughter Sophie, movies, tango, drinking espresso, and playing and listening to rock and roll music. Her main distinction in this latter domain is having formerly been part of "an obscure and very bad band of furry Palo Alto geeks" (according to the Rolling Stones) called Severe Tire Damage. STD was the first band to broadcast live over the Internet. Here in Seattle, she and a bunch of other people in the department get together to make noise semi-regularly (or at least she wishes they did).

     

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