Aller au contenu

Michael Luby

Un article de Wikipédia, l'encyclopédie libre.

Michael George Luby est un informaticien et mathématicien américain, PDG de la compagnie BitRipple, chercheur principal à l'International Computer Science Institute (en), ancien vice-président de la technologie chez Qualcomm, cofondateur et ancien directeur de la technologie de l'entreprise Digital Fountain.

Luby obtient au Massachusetts Institute of Technology un baccalauréat en mathématiques en 1975, et il obtient un doctorat (Ph. D.) en 1983 à l'université de Californie à Berkeley, sous la supervision de Richard M. Karp (Monte-Carlo Methods for Estimating System Reliability[1]).

Il a été boursier postdoctoral (1983-85), professeur assistant (1985-1988), et professeur associé avec titularisation (1988-1990) à l'Université de Toronto. Il a été chef du groupe de théorie à l'Institut international d'informatique (1989-1999). Il a fondé et a été directeur technique de Digital Fountain Inc. (1999-2009), et a été vice-président de la technologie chez Qualcomm (2009-2018) après l'acquisition de Digital Fountain, Inc. par cette dernière.

Luby a apporté des contributions en théorie du codage : les codes tornado (en), qui sont des codes de parité à faible densité pour le codage avec effacement, les codes LT[2] (nommés d'après son nom Luby Transformation codes), une première réalisation de codes fontaine qui sont des codes d'effacement quasi-optimaux, certains codes de Reed-Solomon et à la cryptographie.

Il a montré que toute fonction à sens unique peut être utilisée en cryptographie asymétrique et a analysé, avec Charles Rackoff, le chiffrement par réseau de Feistel[3]. Avec Russell Impagliazzo, Johan Håstad et Leonid Levin, il a prouvé que les générateurs pseudo-aléatoires cryptographiquement sécurisés existent si et seulement si des fonctions à sens unique existent[4] (article pour lequel ils ont reçu le SIAM Outstanding Paper Prize en 2003).

Il a développé les codes tornado, qui sont un exemple de code d'effacement rapide, en l'International Computer Science Institute (ICSI) de Berkeley[5],[6]. Pour la distribution de grandes quantités de données sur un réseau (même avec perte de données) à des groupes d'utilisateurs hétérogènes, il a développé le protocole Digital Fountain basé sur des codes tornado[7]. Les brevets pour les codes tornado et les codes LT sont détenus par la société Digital Fountain.

Luby est également à l'origine d'un algorithme parallèle pour le problème de la recherche d'ensembles indépendants maximaux dans les réseaux[8].

Distinctions

[modifier | modifier le code]

En 2012, Luby a reçu la médaille Richard-Hamming et en 2015 le prix Paris-Kanellakis pour son développement des codes correcteurs d'effacement qui sont devenus importants pour la transmission sans erreur de vidéo en streaming sur les réseaux. En 2015, il est nommé membre de l'Association for Computing Machinery.

Publications

[modifier | modifier le code]
  • Pseudorandomness and cryptographic applications, Princeton University Press, coll. « Princeton Computer Science Notes », , xvi + 234 (ISBN 978-0-691-02546-9).

Notes et références

[modifier | modifier le code]
  1. (en) « Michael George Luby », sur le site du Mathematics Genealogy Project.
  2. Michael Luby, « LT Codes », Proceedings of the 43th IEEE Symposium on the Foundations of Computer Science (FOCS),‎ , p. 271–280
  3. Michael Luby et Charles Rackoff, « How to construct pseudorandom permutations from pseudorandom functions », SIAM J. Comput., vol. 17, no 2,‎ , p. 373-386
  4. Johan Håstad, Russell Impagliazzo, Leonid A. Levin et Michael Luby, « A pseudorandom generator from any one-way function », SIAM J. Comput., vol. 28, no 4,‎ , p. 1364-1396.
  5. Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman et Volker Stemann, « Practical loss-resilient codes », Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (STOC),‎ , p. 150–159.
  6. Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi et Daniel A. Spielman, « Efficient erasure correcting codes », IEEE Trans. Inf. Theory, vol. 47, no 2,‎ , p. 569–584.
  7. Michael Luby, John W. Byers et Michael Mitzenmacher, « A digital fountain approach to asynchronous reliable multicast », IEEE Journal on Selected areas in Communications, vol. 20, no 8,‎ , p. 1528-1540
  8. Michael Luby, « A simple parallel algorithm for the maximal independent set problem », SIAM J. Comput., vol. 15, no 4,‎ , p. 1036-1053.

Liens externes

[modifier | modifier le code]