www.wikidata.de-de.nina.az

Anna Karlin Anna R Karlin 1960 ist eine US amerikanische Informatikerin und Hochschullehrerin an der University of Washi

Anna Karlin

Anna R. Karlin (* 1960) ist eine US-amerikanische Informatikerin und Hochschullehrerin an der University of Washington.

Anna Karlin

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) Bearbeiten

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 Bearbeiten

Einzelnachweise Bearbeiten

  1. Anna Karlin im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
  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
Personendaten
NAME Karlin, Anna
ALTERNATIVNAMEN Karlin, Anna R.
KURZBESCHREIBUNG US-amerikanische Informatikerin
GEBURTSDATUM 1960
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Anna R Karlin 1960 ist eine US amerikanische Informatikerin und Hochschullehrerin an der University of Washington Anna KarlinAnna 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 1 Danach war sie funf Jahre beim DEC Systems Research Center Ab 1994 war sie an der University of Washington an der sie Bill and Melinda Gates Professorin fur 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 veroffentlichte uber Zufalls markierte Paket Marker um IPs zu verfolgen 2 3 kompetitive Analyse von Multiprozessor Cache Koharenz Algorithmen 4 einheitliche Algorithmen um Speicher auf allen Hierarchieebenen zu verwalten 5 kooperatives Web Proxy Caching 6 und Hash Tabellen mit konstanter worst case Nachschlagzeit 7 Sie veroffentlichte auch uber Anwendungen von Algorithmen in den Wirtschaftswissenschaften Preisbildung Auktionen Mit ihren Ko Autoren Yossi Azar Andrei Broder und Eli Upfall fuhrte sie 1994 das Balanced Allocation ausgewogene Zuteilung Paradigma ein 8 9 Dabei geht es um das klassische balls into bins Problem oder balanced allocation in dem n Balle auf m Kasten bins verteilt werden in mehr oder weniger zufalliger Weise Eine Strategie power of two choices wahlt zwei Kasten zufallig aus und legt den Ball in den mit der kleineren Anzahl von Ballen Statt des maximalen Erwartungswerts bei m n von log log n log n displaystyle frac log log n log n bei rein zufalliger Verteilung reduziert das Maximum auf log log n displaystyle log log n und damit exponentiell Das Problem hat viele Anwendungen in der Informatik zum Beispiel gleichmassigere Auslastungen Balancierung bei gemeinsamen Speicherplatzen 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 uber die erwarteten Ruckfragen und wurde in vielfaltiger 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 hochzuverlassige verteilte Datenspeichersysteme bei Microsoft und Dropbox 2020 erhielt sie mit Yossi Azar Andrei Broder Michael Mitzenmacher und Eli Upfal den Paris Kanellakis Preis fur 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 gehort 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 BearbeitenAusser die in den Fussnoten 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 2017Weblinks BearbeitenWebseite an der University of Washington Google ScholarEinzelnachweise Bearbeiten Anna Karlin im Mathematics Genealogy Project englisch Vorlage MathGenealogyProject Wartung id verwendet 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 Stefan Savage David Wetherall Anna Karlin Tom Anderson Network support for IP traceback IEEE ACM Transactions on Networking Band 9 2001 S 226 237 Anna Karlin Mark S Manasse Larry Rudolph Daniel D Sleator Competitive snoopy caching Algorithmica Band 3 2001 S 79 119 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 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 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 Anna Karlin receives ACM Paris Kanellakis Theory and Practice Award Allen School News University of Washington 26 Mai 2021 Azar Broder Karlin Upfal Balanced Allocations SIAM J on Computing Band 29 1999 S 180 200 vorlaufige Version erschienen in Proc STOC 94 ACM 1994Normdaten Person GND 137129092 lobid OGND AKS LCCN n86862911 VIAF 55653867 Wikipedia Personensuche PersonendatenNAME Karlin AnnaALTERNATIVNAMEN Karlin Anna R KURZBESCHREIBUNG US amerikanische InformatikerinGEBURTSDATUM 1960 Abgerufen von https de wikipedia org w index php title Anna Karlin amp oldid 235472036