Anna R. Karlin
Microsoft Professor of Computer Science & Engineering
Allen School of Computer Science &
University of Washington
Seattle, WA 98195-2350
(206) 543-9344 voice
(206) 543-2969 FAX
karlin at cs dot washington dot edu
I am program chair the
2018 ITCS (Innovations in Theoretical Computer Science) conference, which will be held January 11-14, 2018 at MIT.
Here is the program.
The deadline for early registration is December 21.
The deadline for the hotel block is December 28.
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!
Game Theory, Alive with Yuval Peres
The book can be purchased at the American Mathematical Society Bookstore or at amazon.com
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
(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)
(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 )
Cam Thach Nguyen
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
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
"The computer is useless. It can only answer questions."