Michael Luby

Michael George Luby ist ein US-amerikanischer Informatiker.

Luby studierte am Massachusetts Institute of Technology mit dem Bachelor-Abschluss in Mathematik 1975 und wurde 1983 an der University of California, Berkeley, bei Richard M. Karp promoviert (Monte-Carlo Methods for Estimating System Reliability).^[1] Er war Chief Technology Officer von Digital Fountain und ist Vizepräsident für Technologie bei Qualcomm.

Luby leistete Beiträge zur Kodierungstheorie (Tornado Codes, die Low-Density-Parity-Check-Codes für Erasure Coding sind, LT Codes (Luby Transform Codes) als erste Realisierung von Fountain Codes, Cauchy-based Reed-Solomon-Codes) und Kryptographie. Er zeigte, dass beliebige Einwegfunktionen für die Public-Key-Kryptoverfahren benutzt werden können und analysierte mit Charles Rackoff die Feistelchiffre. Mit Russell Impagliazzo, Johan Håstad und Leonid Levin bewies er, dass kryptographisch sichere Pseudozufallsgeneratoren genau dann existieren, wenn Einwegfunktionen existieren (dafür erhielten sie 2003 den SIAM Outstanding Paper Prize).

Tornado Codes, ein Beispiel eines schnellen Erasure Codes, entwickelte er 1996/97 am International Computer Science Institute (ICSI) in Berkeley.^[2] Für die Verteilung großer Mengen von Daten über ein Netz (auch mit Datenverlusten) an heterogene Benutzergruppen entwickelte er das Digital Fountain Protokoll basierend auf Tornado Codes. Die Patente für Tornado Codes und LT Codes werden von Digital Fountain gehalten.

Von ihm stammt auch ein paralleler Algorithmus für das Problem in Netzen maximal unabhängige Mengen zu finden (MIS Problem).

2012 erhielt er die Richard-W.-Hamming-Medaille und 2015 den Paris-Kanellakis-Preis für seine Entwicklung von Erasure Correcting Codes, die wichtig für die fehlerfreie Übertragung von Streaming Video in Netzwerken wurden. 2015 wurde er Fellow der Association for Computing Machinery.

Schriften

A simple parallel algorithm for the maximal independent set problem, SIAM J. Computing, Band 15, 1986, S. 1036–1053
mit Johan Håstad, Russell Impagliazzo, Leonid A Levin: A pseudorandom generator from any one-way function, SIAM J. Computing, Band 28, 1999, S. 1364–1396
mit M. Mitzenmacher, A. Shokrollahi, D. Spielman, V. Stemann: Practical Loss-Resilient Codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (STOC), 1997, S. 150–159
mit Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman: Efficient Erasure Correcting Codes, IEEE Trans. Inform. Theory, Band 47, 2001, S. 569–584
LT Codes, Proceedings of the 43. IEEE Symposium on the Foundations of Computer Science, 2002, S. 271–280.
mit Rackoff: How to construct pseudorandom permutations from pseudorandom functions, SIAM J. Computing, Band 17, 1988, S. 373–386
mit John W. Byers, Michael Mitzenmacher: A digital fountain approach to asynchronous reliable multicast, IEEE Journal on Selected areas in Communications, Band 20, 2002, S. 1528–1540
Pseudorandomness and cryptographic applications, Princeton University Press 1996

Weblinks

Einzelnachweise

↑ Michael Luby im Mathematics Genealogy Project (englisch)
↑ M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, V. Stemann, Practical Loss-Resilient Codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (STOC), 1997, S. 150–159

Personendaten
NAME	Luby, Michael
ALTERNATIVNAMEN	Luby, Michael George (vollständiger Name)
KURZBESCHREIBUNG	US-amerikanischer Informatiker
GEBURTSDATUM	20. Jahrhundert

[1] Michael Luby im Mathematics Genealogy Project (englisch)

[2] M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, V. Stemann, Practical Loss-Resilient Codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (STOC), 1997, S. 150–159

[1]

[2]