Eli Upfal

Eli Upfal (* 1954) ist ein israelischer Informatiker.

Upfal wurde 1983 an der Hebräischen Universität bei Eli Shamir in Informatik promoviert (Distributed Probabilistic Algorithms for Problems in Graph Theory, Communication, Synchronization, and Scheduling) und erhielt dort 1978 einen Bachelor-Abschluss in Mathematik und Statistik. Den Master-Abschluss erhielt er 1980 am Weizmann-Institut. Als Post-Doktorand war er an der University of California, Berkeley, und an der Stanford University. Er war von 1985 bis 1996 Wissenschaftler und Projektmanager (Foundation of Computer Science Gruppe, 1996/97) am IBM Almaden Research Center in Kalifornien und ab 1988 Senior Researcher, ab 1989 Associate Professor und ab 1995 Professor am Weizmann-Institut (von 1992 bis 1997 als Norman D. Cohen Professor). Ab 1998 war er an der Brown University, an der er von 2002 bis 2007 Vorstand der Abteilung Informatik war und Rush C. Hawkins Professor ist.

Er befasst sich mit randomisierten Algorithmen und probabilistischer Analyse von Algorithmen zum Beispiel in kombinatorischer und stochastischer Optimierung, Routing, Kommunikationsnetzwerken, rechnerischer Biologie und Finanzmathematik.

2020 erhielt er mit Anna Karlin, Andrei Broder, Michael Mitzenmacher und Yossi Azar den Paris-Kanellakis-Preis für die Entdeckung und Analyse von ausgewogenen Zuteilungen (balanced allocations), bekannt als Zweierpotenz-Auswahl (power of two choices), und deren umfangreiche Anwendungen in der Praxis (Laudatio). Dabei geht es um das klassische balls-into-bins Problem (oder balanced allocation), in dem Bälle auf Kästen (bins) verteilt werden in mehr oder weniger zufälliger Weise. Eine Strategie (power of two) 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 ${\frac {\log {\log n}}{\log n}}$ bei rein zufälliger Verteilung reduziert das Maximum auf $\log {\log n}$ 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. Upfal war Ko-Autor mit Karlin, Broder und Azar der ursprünglichen Veröffentlichung zur power of two Strategie (STOC 1994).

Zu seinen Doktoranden gehören Oded Regev und Leah Epstein.

2005 wurde er Fellow der Association for Computing Machinery (ACM) und 2002 des IEEE. 1986 und 1993 erhielt er einen IBM Outstanding Innovator Award und 1997 einen IBM Research Division Award.

Schriften (Auswahl)

• mit Michel Mitzenmacher: Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis, Cambridge UP 2017

Weblinks

• Webseite an der Brown University (mit CV)
• Google Scholar