Michael Mitzenmacher

Michael David Mitzenmacher (* 1969) ist ein US-amerikanischer Informatiker und Hochschullehrer an der Harvard University.

Mitzenmacher erhielt seinen Bachelor-Abschluss in Mathematik und Informatik summa cum laude 1991 an der Harvard University, war 1991/92 an der Universität Cambridge (als Churchill Fellow) und wurde 1996 an der University of California, Berkeley, bei Alistair Sinclair promoviert (The Power of Two Choices in Randomized Load Balancing). Danach war er am Digital Systems Research Center in Palo Alto. Ab 1999 war er Assistant Professor an der Harvard University, an der er 2002 Associate Professor und 2005 Professor wurde.

Mit Eli Upfal schrieb er ein Buch über wahrscheinlichkeitstheoretische Methoden und zufallsbasierte Algorithmen in der Informatik. Er ist Experte für Hash-Techniken und das von ihm mit entwickelte MinHash (1998) wird für Dokumentenvergleich von Suchmaschinen im Internet genutzt.

Für seine Arbeiten über Low-Density-Parity-Check-Codes (LDPC) – unter anderem als Mitentwickler der Tornado Codes – erhielt er mit anderen 2002 den IEEE Information Theory Society Best Paper Award und für seine Mitarbeit an Fountain Codes (1998) den 2009 ACM SIGCOMM Test of Time Award. 2020 erhielt er mit Yossi Azar, Andrei Broder, Anna Karlin und Eli Upfal 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 n Bälle auf m 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. Mitzenmacher entwickelte die ursprünglich von Azar, Broder, Karlin und Upfal 1994 veröffentlichte power of two Strategie wesentlich weiter(veröffentlicht in STOC 1995). 2014 wurde er Fellow der Association for Computing Machinery.

Schriften

• M. Adler, S. Chakrabarti, M. Mitzenmacher, L. Rasmussen: Parallel randomized load balancing, in: Proc. 27th Annual ACM Symp. on the Theory of Computing (STOC 95), ACM 1995, S. 238–247
• mit Michael G. Luby, Amin Shokrollahi, Daniel A. Spielman, Volker Stemann: Practical Loss-Resilient Codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing – STOC '97, ACM 1997, S. 150–159.
• mit Andrei Z. Broder, Moses Charikar, Alan M. Frieze: Min-wise independent permutations, Proc. 30th ACM Symposium on Theory of Computing (STOC '98), ACM 1998, S. 327–336
• mit John Byers, Michael Luby, Ashutosh Rege: A Digital Fountain Approach to Reliable Distribution of Bulk Data, Proc. of ACM SIGCOMM 1998
• mit Michael Luby, Amin Shokrollahi, Daniel A. Spielman: Improved Low-Density Parity-Check Codes Using Irregular Graphs, IEEE Trans. Inform. Theory, Februar 2001
• mit Andrea Richa, Ramesh Sitaraman: The power of two random choices: A survey of techniques and results, in: Handbook of Randomized Computing, Band 1, Kluwer, 2001, S. 255–305.
• mit Eli Upfal: Probability and Computing, Cambridge University Press 2005

Weblinks

• Homepage