Michael Luby

from Wikipedia, the free encyclopedia

Michael George Luby is an American computer scientist.

Luby studied at the Massachusetts Institute of Technology with a bachelor's degree in mathematics in 1975 and received his doctorate in 1983 from the University of California, Berkeley , under Richard M. Karp (Monte-Carlo Methods for Estimating System Reliability). He was the chief technology officer of Digital Fountain and is vice president of technology at Qualcomm .

Luby made contributions to coding theory ( tornado codes , which are low-density parity check codes for erasure coding, LT codes (Luby transform codes) as the first realization of fountain codes, Cauchy-based Reed-Solomon codes ) and cryptography . He showed that any one-way functions can be used for the public key crypto method and analyzed the Feistel cipher with Charles Rackoff . With Russell Impagliazzo , Johan Håstad and Leonid Levin , he proved that cryptographically secure pseudo-random generators exist precisely when one-way functions exist (for this they received the SIAM Outstanding Paper Prize in 2003).

He developed Tornado Codes, an example of a fast erasure code, in 1996/97 at the International Computer Science Institute (ICSI) in Berkeley. For the distribution of large amounts of data over a network (also with data loss) to heterogeneous user groups, he developed the Digital Fountain Protocol based on Tornado Codes. The patents for Tornado Codes and LT Codes are held by Digital Fountain.

He also developed a parallel algorithm for the problem of finding maximally independent sets in networks (MIS problem).

In 2012 he received the Richard W. Hamming Medal and in 2015 the Paris Kanellakis Prize for his development of Erasure Correcting Codes , which were important for the error-free transmission of streaming video in networks. In 2015 he became a Fellow of the Association for Computing Machinery .

Fonts

  • A simple parallel algorithm for the maximally independent set problem, SIAM J. Computing, Volume 15, 1986, pp. 1036-1053
  • with Johan Håstad, Russell Impagliazzo, Leonid A Levin: A pseudorandom generator from any one-way function, SIAM J. Computing, Volume 28, 1999, pp. 1364-1396
  • with 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, pp. 150-159
  • with Michael Mitzenmacher , Mohammad Amin Shokrollahi , Daniel A. Spielman : Efficient Erasure Correcting Codes, IEEE Trans. Inform. Theory, Volume 47, 2001, pp. 569-584
  • LT Codes, Proceedings of the 43rd IEEE Symposium on the Foundations of Computer Science, 2002, pp. 271-280.
  • with Rackoff: How to construct pseudorandom permutations from pseudorandom functions, SIAM J. Computing, Volume 17, 1988, pp. 373-386
  • with John W. Byers, Michael Mitzenmacher: A digital fountain approach to asynchronous reliable multicast, IEEE Journal on Selected areas in Communications, Volume 20, 2002, pp. 1528-1540
  • Pseudorandomness and cryptographic applications, Princeton University Press 1996

Web links

Individual evidence

  1. ↑ Michael Luby in the Mathematics Genealogy Project (English)Template: MathGenealogyProject / Maintenance / id used
  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, p. 150– 159
personal data
SURNAME Luby, Michael
ALTERNATIVE NAMES Luby, Michael George (full name)
BRIEF DESCRIPTION American computer scientist
DATE OF BIRTH 20th century