Anna R. Karlin

Karlin became a leader in the field of competitive analysis of online algorithms. Indeed, the terminology competitive analysis, competitive ratio, etc., comes from her 1988 paper with Manasse, Rudolph, and Sleator on Competitive Snoopy Caching. In the area of probabilistic algorithms and probabilistic analysis of algorithms, the most influential of her many results is her work on balanced allocations, known as the power of two choices. Karlin's work has always reached across traditional boundaries. For example, she has done important work at the intersection of systems and theory, at the intersection of networking and theory, at the intersection of data mining and theory (topics such as collaborative filtering and web search), and at the intersection of game theory, economics and algorithms (mechanism design).~