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, kompetitive Analyse von Multiprozessor-Cache-Kohärenz-Algorithmen, einheitliche Algorithmen um Speicher auf allen Hierarchieebenen zu verwalten, kooperatives Web-Proxy-Caching und Hash-Tabellen mit konstanter worst-case Nachschlagzeit. 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. 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

Einzelnachweise

  1. ↑ Anna Karlin im Mathematics Genealogy Project (englisch)
  2. ↑ 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–306
  3. ↑ Stefan Savage, David Wetherall, Anna Karlin, Tom Anderson, Network support for IP traceback, IEEE/ACM Transactions on Networking, Band 9, 2001, S. 226–237
  4. ↑ Anna Karlin, Mark S. Manasse, Larry Rudolph, Daniel D. Sleator, Competitive snoopy caching, Algorithmica, Band 3, 2001, S. 79–119
  5. ↑ 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
  6. ↑ Alec 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
  7. ↑ 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
  8. ↑ Anna Karlin receives ACM Paris Kanellakis Theory and Practice Award, Allen School News, University of Washington 26. Mai 2021
  9. ↑ Azar, 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.