Ken Thompson (Google, formerly Bell Labs)
Ken Thompson is a coauthor and developer of the Unix operating system and worked for many years at Bell Labs before turning to research at Google. He is also the inventor of the B programming language, a precursor of the C programming language.
I am a retired computer scientist. I have won numerous awards (Turing Award, Japan Prize) and am a member of the National Academies of Engineering and Science.
In my senior year at UC Berkeley, Elwyn came and taught a semester course on operating systems. OS was not a well established subject then and also UCB was just experimenting with Computer Science after a long and distinguished reputation in Electrical Engineering. Elwyn and I hit it off immediately. I would rank him as the number one teacher influence in my life.
Specifically, I took his course which, today, would be characterized as “all over the map.” This is understandable, given the time and place. But all aspects of the course were new and exciting.
Most of my interaction with Elwyn during this year was after hours. We would talk about all things that interested us. We discovered that we both loved games. We played a few games, but Elwyn was so intuitively good at any game, I had no chance of beating him. I started programming several games on the university computer. I could only get free computer time after midnight when the computer center was closed. Elwyn would come to the computer center at two in the morning all blurry-eyed to beat the crap out of my latest creation.
Elwyn was a great teacher, he treated me as an equal and inspired me with challenges. I was ambivalent (maybe even a little negative) about going to grad school. Elwyn simply enrolled me without asking. When it came to graduation, Elwyn, again without asking, sicced the Bell Labs recruiter on me. I ended up working at Bell Labs for the next 34 years.
A few years later, Elwyn returned to Bell Labs. He very quickly became the “go to” guy for all things information theory. Whilecreated information theory, Elwyn is one of its biggest contributors. Elwyn’s work has been used in almost all commercial error-correcting applications — CD/DVD, disks, RAID, digital radio/TV satellite/terrestrial — to mention a few.
His work has also been used in military applications such as cryptography code-making, code-breaking, and communications.
In the mid ‘70s, Elwyn was the chairman of the computer science department at Berkeley. He recruited me to teach there for an academic year. During that year, through recruitment, appointments and visitors, he helped transform the department into one of the leading CS departments in the United States.
After that, Elwyn and I had little contact. We mostly interacted through email. He became quite eclectic. He continued working on games, applying his prodigious math skills to improve existing games and develop new ones. He coauthored the best book on the subject — Winning Ways. He mentored many first-class graduate students. He analyzed programs for the Cray-1 computer to maximize the power of this bizarre architecture. He started a hardware/software company for military secure communications — later bought by Kodak. He analyzed trading trends on the futures markets for computer trading.
All in all, he follows his nose, becomes the very best at what interests him. In his wake, he has created many very talented students, enormous commercial applications and several companies. I highly recommend him for the IEEE Medal of Honor. I wonder why it was not presented to him before now.
Madhu Sudan (Harvard University)
Madhu Sudan is a winner of the 2002 Rolf Nevanlinna Prize (awarded by the ICM) and the 2014 Infosys Prize in Mathematics (awarded by the Infosys Science Foundation). Such prizes have recognized his important contributions to probabilistically checkable proofs and the development of error-correcting codes. He was elected to the National Academy of Sciences in 2017.
It is a privilege and high honor to be writing this letter in support of the nomination of Professor Elwyn Berlekamp for the IEEE Medal of Honor. I am enthusiastically in support. Elwyn Berlekamp is a genius of a rare sort who has applied his ingenuity both to the purely theoretical world and to the most applied one. Being a theoretician myself I will focus on the theoretical achievements, from algorithms for decoding, to factorization algorithms for polynomials, and to the theory of games. Each, I believe, is a lasting contribution which will be remembered and taught for centuries. Let me elaborate below.
Coding theory is a key area of applied mathematics that has enabled effective digital communication, something that has completely changed the nature of human society over the past few decades.
A central challenge that had to be overcome to allow such ubiquitous and effective communication is that of errors. Every communication medium is prone to errors, and digital information (unlike sound waves or other analog sources of information) is very fragile — its meaning can change dramatically with a single error. Coding theory is the area that emerged in the 1950s to understand and resolve this challenge. The central object in this theory is an (error-correcting) code which specifies how redundancy may be added to information to make it robust to errors.
Along with this purely mathematical structure a solution needs to be accompanied by efficient algorithms: (1) for encoding, which specifies what redundancy to add, and (2) for decoding, which uses the redundancy to detect if errors have occurred during communication and if so how to fix them.
The challenge of designing error-correcting codes that allow for efficient decoding algorithms is a highly nontrivial one. Indeed, without paying special attention to the structure one may be left with no alternative other than a brute force search among all possible messages, or all possible error patterns, either of which would render the simplest of communication tasks impossible today. One of Berlekamp’s fundamental contributions has been his algorithm for decoding BCH and Reed–Solomon codes. Between the 1970s and 2000s, the Reed–Solomon codes were the most prevalent codes used in storage media (CDs, DVDs, etc.) and Berlekamp’s algorithm was likely employed in most devices for deciphering this information (CD players, DVD players, etc.). The so-called Berlekamp–Massey algorithm is a classic algorithm — it is exceptionally creative and surprisingly effective.
To a purist like me the algorithm remained a bit of a mystery until it was cleared up by a stunning modification to this algorithm, also by Berlekamp with Welch in 1986, which completely clarified the mystery behind this surprising ability to decode Reed–Solomon codes, and enabled significant improvements and vast generalizations. (I have personally benefited from this algorithm and the insight, and it leads to a large portion of my own career.) The ideas behind the Reed–Solomon codes, and their decoding, are algebraic — making use of ideas from college-level algebra (very creatively) to solve the central challenge of communication. In addition to contributing specific ideas to this field, Berlekamp was the person to lead the world on the use of algebraic methods to solve coding theory problems. His text Algebraic Coding Theory published first in 1968 was the only text for over two decades to explain the wonders of this area to the rest of the world. The book is a mix of original research and exposition and many original ideas remain central to the field to this day. Between his patents, his research and this text, Berlekamp’s impact on the theory and practice of error-correcting codes cannot be overstated! They are truly immense.
Turning to other discoveries, one of the remarkable by-products of Elwyn Berlekamp’s interest in coding theory is his algorithm for factoring polynomials — a contribution to one of the most classical questions in mathematics. The factorization question for numbers and polynomials is one that has confounded the greatest of mathematicians for centuries, with, , , , all having made fundamental contributions. Until the twentieth century the understanding was that polynomials of degree five or higher would not find automated solutions since the work had shown there was no closed form solution using radicals. However the story has changed completely now — we know there are efficient algorithms to factor polynomials (and thus “solve” them, in any reasonable sense of the word) over all kinds of domains. The key step here, I believe, is the algorithm of Berlekamp for factoring polynomials over finite fields. This is another radically creative algorithm that blows one’s mind when one first sees it. It was a crucial ingredient in a later algorithm of , and to factor polynomials with rational number coefficients, and together they totally alter our ability to work with polynomials. The impact of this algorithm is a permanent one on the landscape of mathematics.
Finally the last piece I want to talk about is Berlekamp’s contribution to the theory of games. This is another lasting one where the theory produces a surprising analogy between games and numbers and builds a calculus on games (strictly on positions in games), where games can be added and multiplied to lead to new games. The remarkable aspect of this analogy is it allows us to compare games of completely different nature with each other. Once again in the theory of games, in addition to the research, Berlekamp has contributed vastly to its broad understanding by his wonderful series of texts, Winning Ways, withand . It is remarkable to me that a person so focused on the practice of communication, not to mention his other exploits in finance and investments, has been able to simultaneously make such lasting contributions to mathematics and its applications, in pure algebra, in communication theory, and in the study of games. His work will be taught in classes for years to come.
I think this makes him highly deserving of the IEEE Medal of Honor and I support it in the strongest possible terms.
Gordon McKay Professor of Computer Science
John A. Paulson School of Engineering and Applied Science