Michael George Luby is a mathematician and computer scientist, CEO of BitRipple, Senior Research Scientist at the

International Computer Science Institute The International Computer Science Institute (ICSI) is an independent, non-profit research organization located in Berkeley, California, United States. Since its founding in 1988, ICSI has maintained an affiliation agreement with the University ...

(ICSI), former VP Technology at

Qualcomm Qualcomm () is an American multinational corporation headquartered in San Diego, California, and incorporated in Delaware. It creates semiconductors, software, and services related to wireless technology. It owns patents critical to the 5G, 4 ...

, co-founder and former Chief Technology Officer of Digital Fountain. In

coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...

he is known for leading the invention of the Tornado codes and the

LT code In computer science, Luby transform codes (LT codes) are the first class of practical fountain codes that are near-optimal erasure correcting codes. They were invented by Michael Luby in 1998 and published in 2002. Like some other fountain codes, LT ...

s. In cryptography he is known for his contributions showing that any

one-way function In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, spe ...

can be used as the basis for private cryptography, and for his analysis, in collaboration with

Charles Rackoff Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, he attended MIT as both an undergraduate and graduate student, and earned a Ph.D. degree in Computer Science in 1974. He spent a year as a postdoctoral scholar ...

, of the

Feistel cipher In cryptography, a Feistel cipher (also known as Luby–Rackoff block cipher) is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel, who did pioneering research ...

construction. His

distributed algorithm A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific ...

to find a

maximal independent set In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is max ...

in a computer network has also been influential. Luby received his

B.Sc. A Bachelor of Science (BS, BSc, SB, or ScB; from the Latin ') is a bachelor's degree awarded for programs that generally last three to five years. The first university to admit a student to the degree of Bachelor of Science was the University of ...

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

from

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...

in 1975. In 1983 he was awarded a

Ph.D. A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is ...

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

from

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

. In 1996–1997, while at the ICSI, he led the team that invented Tornado codes. These were the first

LDPC code In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. An LDPC code is constructed using a sparse Tanner graph (subclass of the bipa ...

s based on an irregular degree design that has proved crucial to all later good LDPC code designs, which provably achieve channel capacity for the erasure channel, and which have linear time encoding and decoding algorithms. In 1998 Luby left ICSI to found the Digital Fountain company, and shortly thereafter in 1998 he invented the

s, the first practical

fountain code In coding theory, fountain codes (also known as rateless erasure codes) are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the origin ...

s. Qualcomm acquired Digital Fountain in 2009.

Awards

Luby's publications have won the 2002

IEEE Information Theory Society The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operation ...

Information Theory Paper Award for leading the design and analysis of the first irregular LDPC error-correcting codes, the 2003

SIAM Thailand ( ), historically known as Siam () and officially the Kingdom of Thailand, is a country in Southeast Asia, located at the centre of the Mainland Southeast Asia, Indochinese Peninsula, spanning , with a population of almost 70 mi ...

Outstanding Paper Prize for the seminal paper showing how to construct a cryptographically unbreakable pseudo-random generator from any one-way function, and the 2009 ACM SIGCOMM Test of Time Award. In 2016 he was awarded the ACM Edsger W. Dijkstra Prize in Distributed Computing; the prize is given "for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing have been evident for at least a decade", and was awarded to Luby for his work on

parallel algorithm In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machin ...

s for

s. Luby won the 2007 IEEE Eric E. Sumner Award together with

Amin Shokrollahi Amin Shokrollahi (born 1964) is an Iranian mathematician who has worked on a variety of topics including coding theory and algebraic complexity theory. He is best known for his work on iterative decoding of graph based codes for which he receive ...

"for bridging mathematics, Internet design and mobile broadcasting as well as successful standardization". He was given the 2012

IEEE Richard W. Hamming Medal The IEEE Richard W. Hamming Medal is presented annually to up to three persons, for outstanding achievements in information sciences, information systems and information technology. The recipients receive a gold medal, together with a replica in ...

together with Amin Shokrollahi "for the conception, development, and analysis of practical rateless codes". In 2015, he won the ACM

Paris Kanellakis Theory and Practice Award The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery (ACM) to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". It wa ...

"for groundbreaking contributions to erasure correcting codes, which are essential for improving the quality of video transmission over a variety of networks." Luby was elected to the

National Academy of Engineering The National Academy of Engineering (NAE) is an American nonprofit, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy ...

in 2014, "for contributions to coding theory including the inception of rateless codes". In 2015 he was elected as a Fellow of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...

.. Luby was elected as a Fellow of the IEEE in 2009.

Selected publications

* * * * * * * * * * * *

References

{{DEFAULTSORT:Luby, Michael Living people Modern cryptographers American cryptographers American information theorists Massachusetts Institute of Technology School of Science alumni University of California, Berkeley alumni Theoretical computer scientists Researchers in distributed computing American chief technology officers Fellows of the Association for Computing Machinery Members of the United States National Academy of Engineering Year of birth missing (living people)