mini|Anna Karlin Anna R. Karlin (* 1960) ist eine US-amerikanische Informatikerin und Hochschullehrerin an der University of Washington.
Anna Karlin ist die Tochter des Mathematikers Samuel Karlin. Sie studierte an der Stanford University mit dem Bachelor-Abschluss 1981 und der Promotion bei Jeffrey Ullman 1987 (Sharing Memory in Distributed Systems - Methods and Application). Danach war sie fünf Jahre beim DEC Systems Research Center. Ab 1994 war sie an der University of Washington, an der sie Bill and Melinda Gates Professorin für Informatik an der Paul G. Allen School of Computer Science and Engineering ist.
Sie entwirft und analysiert vor allem Zufalls-Algorithmen (sogenannte randomisierte oder probabilistische Algorithmen) und Online-Algorithmen, zum Beispiel im Bereich verteiltes Rechnen, Data Mining, Systemsoftware und Betriebssysteme, Computernetzwerke, algorithmische Spieltheorie. Sie veröffentlichte über Zufalls-markierte Paket-Marker, um IPs zu verfolgen,Stefan Savage, David Wetherall, Anna Karlin, Tom Anderson, Practical network support for IP traceback, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM '00), 2000, S. 295–306Stefan Savage, David Wetherall, Anna Karlin, Tom Anderson, Network support for IP traceback, IEEE/ACM Transactions on Networking, Band 9, 2001, S. 226–237 kompetitive Analyse von Multiprozessor-Cache-Kohärenz-Algorithmen,Anna Karlin, Mark S. Manasse, Larry Rudolph, Daniel D. Sleator, Competitive snoopy caching, Algorithmica, Band 3, 2001, S. 79–119 einheitliche Algorithmen um Speicher auf allen Hierarchieebenen zu verwalten,M. J. Feeley, A. R. Karlin, C.A. Thekkath u. a., Implementing global memory management in a workstation cluster, Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP '95), 1995, S. 201–212 kooperatives Web-Proxy-CachingAlec Wolman, Anna Karlin, Henry M. Levy u. a.: On the scale and performance of cooperative Web proxy caching, Proceedings of the 17th ACM Symposium on Operating Systems Principles (SOSP '99), 1999, S. 16–31 und Hash-Tabellen mit konstanter worst-case Nachschlagzeit.Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, Robert E. Tarjan, Dynamic perfect hashing: upper and lower bounds, SIAM Journal on Computing, Band 23, 1994, S. 738–761 Sie veröffentlichte auch über Anwendungen von Algorithmen in den Wirtschaftswissenschaften (Preisbildung, Auktionen).
Mit ihren Ko-Autoren Yossi Azar, Andrei Broder und Eli Upfall führte sie 1994 das Balanced Allocation (ausgewogene Zuteilung) Paradigma ein.Anna Karlin receives ACM Paris Kanellakis Theory and Practice Award, Allen School News, University of Washington 26. Mai 2021Azar, Broder, Karlin, Upfal, Balanced Allocations, SIAM J. on Computing, Band 29, 1999, S. 180–200, vorläufige Version erschienen in Proc. STOC 94, ACM 1994 Dabei geht es um das klassische balls-into-bins Problem (oder balanced allocation), in dem n Bälle auf m Kästen (bins) verteilt werden in mehr oder weniger zufälliger Weise. Eine Strategie (power of two choices) wählt zwei Kästen zufällig aus und legt den Ball in den mit der kleineren Anzahl von Bällen. Statt des maximalen Erwartungswerts (bei m=n) von bei rein zufälliger Verteilung reduziert das Maximum auf und damit exponentiell. Das Problem hat viele Anwendungen in der Informatik, zum Beispiel gleichmäßigere Auslastungen (Balancierung) bei gemeinsamen Speicherplätzen, Verteilung von Informationspaketen auf parallele Routen in Web-Servern und Netzwerken, Hash-Tabellen. Er erfordert nur Entscheidungen auf lokaler Ebene, eine Form zentraler Kontrolle oder Kenntnis über die erwarteten Rückfragen und wurde in vielfältiger Weise weiterentwickelt. Die Einfachheit der Strategie war unerwartet und sie wurde ein neues Paradigma in der Algorithmentheorie. Anwendungen fand sie zum Beispiel beim Web-Index von iGoogle, im Overlay-Netz von Akamai und hochzuverlässige verteilte Datenspeichersysteme bei Microsoft und Dropbox.
2020 erhielt sie mit Yossi Azar, Andrei Broder, Michael Mitzenmacher und Eli Upfal den Paris-Kanellakis-Preis für die Entdeckung und Analyse von ausgewogenen Zuteilungen (balanced allocations), bekannt als „power of two choices“, und deren umfangreiche Anwendungen in der Praxis (Laudatio). 2012 wurde sie Fellow der Association for Computing Machinery, 2016 Fellow der American Academy of Arts and Sciences, 2021 Mitglied der National Academy of Sciences und 2022 der National Academy of Engineering.
1997 war sie Vorsitzende des Programmkomitees des IEEE Symposiums on Foundations of Computer Science.
Zu ihren Doktoranden gehört Frank McSherry.
Mit anderen Mitgliedern von DEC Systems Research spielte sie in der Garagen-Rockband Severe Tire Damage (Gesang, Gitarre) in Palo Alto.
Schriften (Auswahl) Außer die in den Fußnoten zitierten Arbeiten.
A. R. Karlin, M. S. Manasse, L. A. McGeoch, S. Owicki: Competitive randomized algorithms for nonuniform problems, Algorithmica, Band 11, 1994, S. 542–571 P. Cao, E. W. Felten, A. R. Karlin, K. Li: A study of integrated prefetching and caching strategies, ACM SIGMETRICS Performance Evaluation Review, Band 23, 1995, S. 188–197 Y. Azar, A. Fiat, A. R. Karlin, F. McSherry, J. Saia: Spectral analysis of data, Proc. 33th Annual ACM Symp. on the Theory of Computing (STOC 2001), ACM 2001, S. 619–626 V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Keynon, F. McSherry: On profit-maximizing envy-free pricing, Proc. 16th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 2005, S. 1164–1173 A. V. Goldberg, J. D. Hartline, A. R. Karlin, M. Saks, A. Wright: Competitive auctions, Games and Economic Behavior, Band 55, 2006, S. 242–269 Anna Karlin, Yuval Peres: Game Theory, Alive, Providence, Rhode Island: American Mathematical Society 2017
Weblinks Webseite an der University of Washington Google Scholar
Einzelnachweise
Kategorie:Informatiker Kategorie:Hochschullehrer (University of Washington) Kategorie:Mitglied der American Academy of Arts and Sciences Kategorie:Mitglied der National Academy of Sciences Kategorie:Mitglied der National Academy of Engineering Kategorie:US-Amerikaner Kategorie:Geboren 1960 Kategorie:Frau