Michael George Luby is a mathematician and computer scientist, VP Technology at Qualcomm

Qualcomm

Qualcomm is an American global telecommunication corporation that designs, manufactures and markets digital wireless telecommunications products and services based on its code division multiple access technology and other technologies. Headquartered in San Diego, CA, USA...

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

Coding theory

Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

 he is known for leading the invention of the Tornado codes and the LT codes. In cryptography he is known for his contributions showing that any one-way function

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, specifically the theory of polynomial time problems...

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

Charles Rackoff

Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, Rackoff 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 at INRIA in France.He currently works at the...

, of the Feistel cipher

Feistel cipher

In cryptography, a Feistel 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 while working for IBM ; it is also commonly known as a Feistel network. A large proportion of block...

 construction. His distributed algorithm to find a maximal independent set

Maximal independent set

In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S...

 in a computer network has also been very influential. He has also contributed to average-case complexity

Average-case complexity

Average-case complexity is a subfield of computational complexity theory that studies the complexity of algorithms on random inputs.The study of average-case complexity has applications in the theory of cryptography....

.

Luby received his B.Sc. in mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 from MIT in 1975. In 1983 he was awarded a Ph.D.

Ph.D.

A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...

 in computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 from UC Berkeley. In 1996-1997, while at the International Computer Science Institute

International Computer Science Institute

The International Computer Science Institute is an independent, non-profit research organization located in Berkeley, California, USA. Since its founding in 1988, ICSI has maintained an affiliation with the University of California, Berkeley, where several of its members hold faculty appointments...

, he led the team that invented Tornado codes. These were the first LDPC codes based on an irregular degree design that has proved crucial to all later good LDPC code designs, which provably achieve channel capacity

Channel capacity

In electrical engineering, computer science and information theory, channel capacity is the tightest upper bound on the amount of information that can be reliably transmitted over a communications channel...

 for the erasure channel

Binary erasure channel

A binary erasure channel is a common communications channel model used in coding theory and information theory. In this model, a transmitter sends a bit , and the receiver either receives the bit or it receives a message that the bit was not received...

, and which have linear time encoding and decoding algorithms. In 1998 Luby left ICSI

ICSI

The abbreviation ICSI may refer to:* Intracytoplasmic sperm injection, a medical technique used in assisted reproduction* International Computer Science Institute, a non-profit research lab in Berkeley, California...

 to found the Digital Fountain company, and shortly thereafter in 1998 he invented the LT codes, the first practical fountain code

Fountain code

In coding theory, fountain 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 original source symbols can ideally be recovered from any subset of the encoding symbols of...

s. Qualcomm aqcuired Digital Fountain in 2009.

Awards received

• 2002 IEEE Information Theory Society Information Theory Paper Award for leading the design and analysis of the first irregular LDPC error-correcting codes
• 2003 SIAM Outstanding Paper Prize for the seminal paper showing how to construct a cryptographically unbreakable pseudo-random generator from any one-way function
• 2007 IEEE Eric E. Sumner Communications Theory Award for outstanding contributions to communications technology