Celebratio Mathematica

Ken Thompson is a coau­thor and de­veloper of the Unix op­er­at­ing sys­tem and worked for many years at Bell Labs be­fore turn­ing to re­search at Google. He is also the in­vent­or of the B pro­gram­ming lan­guage, a pre­curs­or of the C pro­gram­ming lan­guage.

I am a re­tired com­puter sci­ent­ist. I have won nu­mer­ous awards (Tur­ing Award, Ja­pan Prize) and am a mem­ber of the Na­tion­al Academies of En­gin­eer­ing and Sci­ence.

In my seni­or year at UC Berke­ley, El­wyn came and taught a semester course on op­er­at­ing sys­tems. OS was not a well es­tab­lished sub­ject then and also UCB was just ex­per­i­ment­ing with Com­puter Sci­ence after a long and dis­tin­guished repu­ta­tion in Elec­tric­al En­gin­eer­ing. El­wyn and I hit it off im­me­di­ately. I would rank him as the num­ber one teach­er in­flu­ence in my life.

Spe­cific­ally, I took his course which, today, would be char­ac­ter­ized as “all over the map.” This is un­der­stand­able, giv­en the time and place. But all as­pects of the course were new and ex­cit­ing.

Most of my in­ter­ac­tion with El­wyn dur­ing this year was after hours. We would talk about all things that in­ter­ested us. We dis­covered that we both loved games. We played a few games, but El­wyn was so in­tu­it­ively good at any game, I had no chance of beat­ing him. I star­ted pro­gram­ming sev­er­al games on the uni­versity com­puter. I could only get free com­puter time after mid­night when the com­puter cen­ter was closed. El­wyn would come to the com­puter cen­ter at two in the morn­ing all blurry-eyed to beat the crap out of my latest cre­ation.

El­wyn was a great teach­er, he treated me as an equal and in­spired me with chal­lenges. I was am­bi­val­ent (maybe even a little neg­at­ive) about go­ing to grad school. El­wyn simply en­rolled me without ask­ing. When it came to gradu­ation, El­wyn, again without ask­ing, sicced the Bell Labs re­cruit­er on me. I ended up work­ing at Bell Labs for the next 34 years.

A few years later, El­wyn re­turned to Bell Labs. He very quickly be­came the “go to” guy for all things in­form­a­tion the­ory. While Claude Shan­non cre­ated in­form­a­tion the­ory, El­wyn is one of its biggest con­trib­ut­ors. El­wyn’s work has been used in al­most all com­mer­cial er­ror-cor­rect­ing ap­plic­a­tions — CD/DVD, disks, RAID, di­git­al ra­dio/TV satel­lite/ter­restri­al — to men­tion a few.

His work has also been used in mil­it­ary ap­plic­a­tions such as cryp­to­graphy code-mak­ing, code-break­ing, and com­mu­nic­a­tions.

In the mid ‘70s, El­wyn was the chair­man of the com­puter sci­ence de­part­ment at Berke­ley. He re­cruited me to teach there for an aca­dem­ic year. Dur­ing that year, through re­cruit­ment, ap­point­ments and vis­it­ors, he helped trans­form the de­part­ment in­to one of the lead­ing CS de­part­ments in the United States.

After that, El­wyn and I had little con­tact. We mostly in­ter­ac­ted through email. He be­came quite ec­lect­ic. He con­tin­ued work­ing on games, ap­ply­ing his prodi­gious math skills to im­prove ex­ist­ing games and de­vel­op new ones. He coau­thored the best book on the sub­ject — Win­ning Ways. He ment­ored many first-class gradu­ate stu­dents. He ana­lyzed pro­grams for the Cray-1 com­puter to max­im­ize the power of this bizarre ar­chi­tec­ture. He star­ted a hard­ware/soft­ware com­pany for mil­it­ary se­cure com­mu­nic­a­tions — later bought by Kodak. He ana­lyzed trad­ing trends on the fu­tures mar­kets for com­puter trad­ing.

All in all, he fol­lows his nose, be­comes the very best at what in­terests him. In his wake, he has cre­ated many very tal­en­ted stu­dents, enorm­ous com­mer­cial ap­plic­a­tions and sev­er­al com­pan­ies. I highly re­com­mend him for the IEEE Medal of Hon­or. I won­der why it was not presen­ted to him be­fore now.

Madhu Su­dan is a win­ner of the 2002 Rolf Nevan­linna Prize (awar­ded by the ICM) and the 2014 In­fosys Prize in Math­em­at­ics (awar­ded by the In­fosys Sci­ence Found­a­tion). Such prizes have re­cog­nized his im­port­ant con­tri­bu­tions to prob­ab­il­ist­ic­ally check­able proofs and the de­vel­op­ment of er­ror-cor­rect­ing codes. He was elec­ted to the Na­tion­al Academy of Sci­ences in 2017.

Dear Col­leagues:

It is a priv­ilege and high hon­or to be writ­ing this let­ter in sup­port of the nom­in­a­tion of Pro­fess­or El­wyn Ber­lekamp for the IEEE Medal of Hon­or. I am en­thu­si­ast­ic­ally in sup­port. El­wyn Ber­lekamp is a geni­us of a rare sort who has ap­plied his in­genu­ity both to the purely the­or­et­ic­al world and to the most ap­plied one. Be­ing a the­or­eti­cian my­self I will fo­cus on the the­or­et­ic­al achieve­ments, from al­gorithms for de­cod­ing, to fac­tor­iz­a­tion al­gorithms for poly­no­mi­als, and to the the­ory of games. Each, I be­lieve, is a last­ing con­tri­bu­tion which will be re­membered and taught for cen­tur­ies. Let me elab­or­ate be­low.

Cod­ing the­ory is a key area of ap­plied math­em­at­ics that has en­abled ef­fect­ive di­git­al com­mu­nic­a­tion, something that has com­pletely changed the nature of hu­man so­ci­ety over the past few dec­ades.

A cent­ral chal­lenge that had to be over­come to al­low such ubi­quit­ous and ef­fect­ive com­mu­nic­a­tion is that of er­rors. Every com­mu­nic­a­tion me­di­um is prone to er­rors, and di­git­al in­form­a­tion (un­like sound waves or oth­er ana­log sources of in­form­a­tion) is very fra­gile — its mean­ing can change dra­mat­ic­ally with a single er­ror. Cod­ing the­ory is the area that emerged in the 1950s to un­der­stand and re­solve this chal­lenge. The cent­ral ob­ject in this the­ory is an (er­ror-cor­rect­ing) code which spe­cifies how re­dund­ancy may be ad­ded to in­form­a­tion to make it ro­bust to er­rors.

Along with this purely math­em­at­ic­al struc­ture a solu­tion needs to be ac­com­pan­ied by ef­fi­cient al­gorithms: (1) for en­cod­ing, which spe­cifies what re­dund­ancy to add, and (2) for de­cod­ing, which uses the re­dund­ancy to de­tect if er­rors have oc­curred dur­ing com­mu­nic­a­tion and if so how to fix them.

The chal­lenge of design­ing er­ror-cor­rect­ing codes that al­low for ef­fi­cient de­cod­ing al­gorithms is a highly non­trivi­al one. In­deed, without pay­ing spe­cial at­ten­tion to the struc­ture one may be left with no al­tern­at­ive oth­er than a brute force search among all pos­sible mes­sages, or all pos­sible er­ror pat­terns, either of which would render the simplest of com­mu­nic­a­tion tasks im­possible today. One of Ber­lekamp’s fun­da­ment­al con­tri­bu­tions has been his al­gorithm for de­cod­ing BCH and Reed–So­lomon codes. Between the 1970s and 2000s, the Reed–So­lomon codes were the most pre­val­ent codes used in stor­age me­dia (CDs, DVDs, etc.) and Ber­lekamp’s al­gorithm was likely em­ployed in most devices for de­ci­pher­ing this in­form­a­tion (CD play­ers, DVD play­ers, etc.). The so-called Ber­lekamp–Mas­sey al­gorithm is a clas­sic al­gorithm — it is ex­cep­tion­ally cre­at­ive and sur­pris­ingly ef­fect­ive.

To a pur­ist like me the al­gorithm re­mained a bit of a mys­tery un­til it was cleared up by a stun­ning modi­fic­a­tion to this al­gorithm, also by Ber­lekamp with Welch in 1986, which com­pletely cla­ri­fied the mys­tery be­hind this sur­pris­ing abil­ity to de­code Reed–So­lomon codes, and en­abled sig­ni­fic­ant im­prove­ments and vast gen­er­al­iz­a­tions. (I have per­son­ally be­nefited from this al­gorithm and the in­sight, and it leads to a large por­tion of my own ca­reer.) The ideas be­hind the Reed–So­lomon codes, and their de­cod­ing, are al­geb­ra­ic — mak­ing use of ideas from col­lege-level al­gebra (very cre­at­ively) to solve the cent­ral chal­lenge of com­mu­nic­a­tion. In ad­di­tion to con­trib­ut­ing spe­cif­ic ideas to this field, Ber­lekamp was the per­son to lead the world on the use of al­geb­ra­ic meth­ods to solve cod­ing the­ory prob­lems. His text Al­geb­ra­ic Cod­ing The­ory pub­lished first in 1968 was the only text for over two dec­ades to ex­plain the won­ders of this area to the rest of the world. The book is a mix of ori­gin­al re­search and ex­pos­i­tion and many ori­gin­al ideas re­main cent­ral to the field to this day. Between his pat­ents, his re­search and this text, Ber­lekamp’s im­pact on the the­ory and prac­tice of er­ror-cor­rect­ing codes can­not be over­stated! They are truly im­mense.

Turn­ing to oth­er dis­cov­er­ies, one of the re­mark­able by-products of El­wyn Ber­lekamp’s in­terest in cod­ing the­ory is his al­gorithm for factor­ing poly­no­mi­als — a con­tri­bu­tion to one of the most clas­sic­al ques­tions in math­em­at­ics. The fac­tor­iz­a­tion ques­tion for num­bers and poly­no­mi­als is one that has con­foun­ded the greatest of math­em­aticians for cen­tur­ies, with Card­ano, Tartaglia, Abel, Galois, all hav­ing made fun­da­ment­al con­tri­bu­tions. Un­til the twen­ti­eth cen­tury the un­der­stand­ing was that poly­no­mi­als of de­gree five or high­er would not find auto­mated solu­tions since the work had shown there was no closed form solu­tion us­ing rad­ic­als. However the story has changed com­pletely now — we know there are ef­fi­cient al­gorithms to factor poly­no­mi­als (and thus “solve” them, in any reas­on­able sense of the word) over all kinds of do­mains. The key step here, I be­lieve, is the al­gorithm of Ber­lekamp for factor­ing poly­no­mi­als over fi­nite fields. This is an­oth­er rad­ic­ally cre­at­ive al­gorithm that blows one’s mind when one first sees it. It was a cru­cial in­gredi­ent in a later al­gorithm of Len­stra, Len­stra and Lovász to factor poly­no­mi­als with ra­tion­al num­ber coef­fi­cients, and to­geth­er they totally al­ter our abil­ity to work with poly­no­mi­als. The im­pact of this al­gorithm is a per­man­ent one on the land­scape of math­em­at­ics.

Fi­nally the last piece I want to talk about is Ber­lekamp’s con­tri­bu­tion to the the­ory of games. This is an­oth­er last­ing one where the the­ory pro­duces a sur­pris­ing ana­logy between games and num­bers and builds a cal­cu­lus on games (strictly on po­s­i­tions in games), where games can be ad­ded and mul­ti­plied to lead to new games. The re­mark­able as­pect of this ana­logy is it al­lows us to com­pare games of com­pletely dif­fer­ent nature with each oth­er. Once again in the the­ory of games, in ad­di­tion to the re­search, Ber­lekamp has con­trib­uted vastly to its broad un­der­stand­ing by his won­der­ful series of texts, Win­ning Ways, with Con­way and Guy. It is re­mark­able to me that a per­son so fo­cused on the prac­tice of com­mu­nic­a­tion, not to men­tion his oth­er ex­ploits in fin­ance and in­vest­ments, has been able to sim­ul­tan­eously make such last­ing con­tri­bu­tions to math­em­at­ics and its ap­plic­a­tions, in pure al­gebra, in com­mu­nic­a­tion the­ory, and in the study of games. His work will be taught in classes for years to come.

I think this makes him highly de­serving of the IEEE Medal of Hon­or and I sup­port it in the strongest pos­sible terms.

Sin­cerely,

Madhu Su­dan
Gor­don McKay Pro­fess­or of Com­puter Sci­ence
John A. Paulson School of En­gin­eer­ing and Ap­plied Sci­ence
Har­vard Uni­versity