Celebratio Mathematica

El­wyn Ber­lekamp passed away on April 9, 2019 in Berke­ley, Cali­for­nia. He was a bril­liant math­em­atician and en­gin­eer who did ground­break­ing re­search in In­form­a­tion The­ory and Game The­ory. He was also a suc­cess­ful en­tre­pren­eur, helped cre­ate the most prof­it­able quant fund, served lead­er­ship roles for aca­dem­ic so­ci­et­ies, and was a gen­er­ous sup­port­er of STEM edu­ca­tion and math­em­at­ics re­search. El­wyn is sur­vived by his wife, Jen­nifer; daugh­ters Per­sis, an art his­tor­i­an at the Uni­versity of Chica­go, and Bron­wen Ber­lekamp O’Wril of Port­land, Maine; and son Dav­id of Oak­land.

El­wyn was the smartest stu­dent I met at MIT. He took ex­tra courses dur­ing his un­der­gradu­ate years, com­plet­ing his BS and MS de­grees after 4 years and his PhD two years later, all at MIT. In ad­di­tion, he taught him­self Rus­si­an and to­geth­er with oth­er un­der­gradu­ate stu­dents de­veloped the first chess play­ing soft­ware pro­gram which is fea­tured in the Com­puter His­tory Mu­seum in Moun­tain View, Cali­for­nia. Al­though an Elec­tric­al En­gin­eer­ing stu­dent, he was among five win­ners of the na­tion­al Put­nam Math­em­at­ics com­pet­i­tion in Decem­ber 1961. His PhD thes­is, Block Cod­ing with Noise­less Feed­back, spawned sev­er­al pub­lic­a­tions. One key idea was to re­cast the prob­lem as an asym­met­ric com­bin­at­or­i­al game between the Coder and the Noise­maker and then to find asymp­tot­ic­ally op­tim­um strategies for play­ing that game. This was fol­lowed by his ground­break­ing re­search work in In­form­a­tion The­ory, Math­em­at­ics, and Game The­ory. Less know is his mostly clas­si­fied con­sult­ing work on cryp­to­graph­ic re­search for the In­sti­tute for De­fense Ana­lys­is (IDA) in Prin­ceton, New Jer­sey.

In ad­di­tion to his long ca­reer at the Uni­versity of Cali­for­nia Berke­ley, El­wyn worked for short peri­ods at Bell Labs, Jet Propul­sion Labor­at­ory (JPL), and IDA.

He in­ven­ted a series of al­gorithms and im­ple­ment­a­tions which made power­ful er­ror-cor­rect­ing codes use­ful for many ap­plic­a­tions. Best known among these res­ults was his al­gorithm to factor poly­no­mi­als over fi­nite fields and the Ber­lekamp–Mas­sey al­gorithm to find lin­ear re­cur­sions in long data streams. These were pub­lished in his 1968 book, Al­geb­ra­ic Cod­ing The­ory. An­oth­er ma­jor new res­ult in that book was the enu­mer­a­tion of the num­ber of in­form­a­tion bits in long bin­ary BCH codes. This book won the IEEE In­form­a­tion The­ory’s an­nu­al best re­search pa­per award. The ap­plic­ab­il­ity of some of these al­gorithms to prob­lems in cryp­to­graphy at­trac­ted the at­ten­tion of the Na­tion­al Se­cur­ity Agency (NSA), who in 1967–1968 re­cruited El­wyn to be­come a con­sult­ant to their re­search group at the IDA.

Some be­lieved that El­wyn’s al­gorithms were im­prac­tic­al. Without any an­gel in­vestors or ven­ture cap­it­al, he foun­ded Cyc­lo­tom­ics to de­vel­op com­mer­cial im­ple­ment­a­tions start­ing with the world’s fore­most Galois Field com­puter which shattered the then-pre­val­ent myth that power­ful high-speed al­geb­ra­ic er­ror-cor­rec­tion was not feas­ible. When I met him dur­ing this peri­od, I was amazed to see El­wyn pro­gram­ming an early mi­cro­pro­cessor and design­ing in­teg­rated cir­cuits. This work led to El­wyn be­com­ing the young­est mem­ber of the Na­tion­al Academy of En­gin­eer­ing in 1977.

Cyc­lo­tom­ics boot­strapped its growth by prof­it­able sales, and even­tu­ally grew to a peak of 40 people. It worked with NASA and de­signed and built the er­ror-cor­rec­tion de­coders for the down­link of the Hubble Space Tele­scope. Bey­ond com­mu­nic­a­tions, Cyc­lo­tom­ics also pi­on­eered ap­plic­a­tions of al­geb­ra­ic er­ror-cor­rec­tion tech­no­logy to sev­er­al data stor­age tech­no­lo­gies, in­clud­ing mag­net­ic tapes, mag­net­ic discs, and op­tic­al discs. By the mid-1980s, there were over 40 US com­pan­ies try­ing to de­vel­op read-write op­tic­al memor­ies. Cyc­lo­tom­ics de­veloped con­trol­lers for sev­er­al of them. The biggest of these com­pan­ies was East­man Kodak which ac­quired Cyc­lo­tom­ics in 1985.

In 1984 Cyc­lo­tom­ics spun off its con­sult­ing con­tracts in cryp­to­graphy to a new star­tup which be­came known as Cylink which I had co-foun­ded with El­wyn and oth­ers. Cylink ob­tained an­gel fund­ing from a group formed by Jim Si­mons whom El­wyn had met at an IDA in­ter­view in 1967. In 1996 Cylink went pub­lic on NAS­DAQ.

Si­mons had star­ted a hedge fund man­age­ment firm which be­came Renais­sance Tech­no­lo­gies in 1982. Six years later Renais­sance es­tab­lished the Medal­lion quant fund us­ing Le­onard Baum’s math­em­at­ic­al mod­els which were im­proved by pi­on­eer­ing al­geb­ra­ist James Ax to ex­plore cor­rel­a­tions from which they could profit. Around 1989 this fund, then with Ax as CEO and called Ax­com, was not do­ing well. Hav­ing met again as mem­bers of Cylink’s board of dir­ect­ors, Si­mons turned to El­wyn to run Medal­lion from Berke­ley, Cali­for­nia. El­wyn bought out most of Ax’s stake in Ax­com and be­came its CEO. Over a six-month peri­od, he worked with Si­mons, Sandor Straus, and con­sult­ant Henry Laufer to over­haul Medal­lion’s trad­ing sys­tem. In 1990 El­wyn led Medal­lion to a 55.9% gain, net of fees, and then re­turned to teach­ing at the Uni­versity of Cali­for­nia Berke­ley after selling out his shares to Si­mons at six times the price for which he had bought his Ax­com in­terests 16 months earli­er. Straus took the reins of Medal­lion’s re­vamped trad­ing sys­tem, and Medal­lion re­turned 39.4% in 1991, 34% in 1992 and 39.1% in 1993. They con­tin­ued hir­ing math­em­aticians, en­gin­eers, and sci­ent­ists and ex­pan­ded in­to trad­ing stocks as well as fu­tures. The Medal­lion fund be­came the most suc­cess­ful hedge fund, av­er­aging a 71.8% an­nu­al re­turn, be­fore fees, from 1994 through mid-2014. It made Si­mons the lead­ing fund man­ager on Wall Street.

In late 2000, four new part­ners and El­wyn launched an­oth­er quant­it­at­ively man­aged fund, called Berke­ley Quant­it­at­ive (BQ). After two years of de­vel­op­ment and stud­ies, it ac­cep­ted money from out­side in­vestors and began trad­ing. As more in­vestors entered, the fund size grew. Net per­form­ance reached 17%, and the fund size reached \$250 mil­lion about 1.5 years after trad­ing had be­gun. But the next couple of months saw un­friendly mar­ket con­di­tions ag­grav­ated by BQ’s in­tern­al or­gan­iz­a­tion­al prob­lems. BQ paid all of its debts and closed down. The ini­tial in­vestors real­ized a net re­turn of about 2% after about 3 years. El­wyn felt that BQ was not a suc­cess, but did much bet­ter than the wipe-outs ex­per­i­enced by most star­tups.

El­wyn’s fas­cin­a­tion with math­em­at­ic­al games began when he learned to play Dots-and-Boxes in the first grade. Years later he dis­covered sev­er­al math­em­at­ic­al the­or­ems which un­der­lie this game and oth­ers. In math­em­at­ics, his best-known work was on com­bin­at­or­i­al game the­ory, partly dis­sem­in­ated in his four-volume work Win­ning Ways with John H. Con­way and Richard Guy. Ac­cord­ing to Mar­tin Gard­ner, au­thor of the ex­tremely pop­u­lar “Math­em­at­ic­al Games” column in Sci­entif­ic Amer­ic­an from 1957 to 1982, Win­ning Ways was the “greatest con­tri­bu­tion of the 20th cen­tury to the bur­geon­ing field of re­cre­ation­al math­em­at­ics. No oth­er work has been so packed with com­pletely new and sig­ni­fic­ant ma­ter­i­al, or presen­ted with so much wit, depth, and clar­ity.” These books also be­came the found­a­tion of a less-re­cre­ation­al sub­ject called Com­bin­at­or­i­al Game The­ory. It was of­fi­cially ac­cep­ted by Math Re­views (now Math­S­ciNet) as a new branch of math­em­at­ics and at­trac­ted the in­terest and con­tri­bu­tions of many math­em­aticians and com­puter sci­ent­ists.

El­wyn’s later ac­com­plish­ment in game the­ory was his ana­lys­is of po­s­i­tions in the en­dgame of Go. With Dav­id Wolfe, he pub­lished the book Math­em­at­ic­al Go. He demon­strated the ef­fect­ive­ness of his the­ory by set­ting up a plaus­ible en­dgame po­s­i­tion from which he beat one of the Ja­pan­ese cham­pi­ons of the game, after which he set up the same po­s­i­tion, re­versed the board, and beat the mas­ter a second time. He also in­ven­ted a vari­ation of the game called Coupon Go, which is closer to el­eg­ant math­em­at­ic­al the­or­ies. This at­trac­ted the at­ten­tion of both math­em­aticians and sev­er­al world-class pro­fes­sion­al Go play­ers.

El­wyn’s fath­er was a min­is­ter, and one sees the fath­er’s in­flu­ence on the son in a strong and con­sist­ent ideal of ser­vice to the great­er good. El­wyn was act­ive in the pop­ular­iz­a­tion of Sci­ence, Tech­no­logy, En­gin­eer­ing and Math­em­at­ics (STEM), dir­ec­ted both at K-12 edu­ca­tion and at adults. He served on the gov­ern­ing boards of each of the two fore­most private schools in Oak­land, Cali­for­nia, Col­lege Pre­par­at­ory School and Head-Royce. He also dir­ec­ted his ef­forts to­wards ex­tra­cur­ricular edu­ca­tion. In the late 1970s, he helped fin­ance the start of the Berke­ley Math Circle for ju­ni­or high school stu­dents who met in a classroom one even­ing per week to share and en­joy solv­ing math or lo­gic prob­lems not covered in their school cur­ricula. He felt that one key to the suc­cess of such ef­forts was to erad­ic­ate (or at least blur) the line many stu­dents ima­gine between “real” math­em­at­ics/en­gin­eer­ing and “re­cre­ation­al math­em­at­ics.” Since 2015 he de­voted much of his time to the pre­par­a­tion of short in­tro­duct­ory videos aimed at get­ting more ju­ni­or high school stu­dents in­ter­ested in com­bin­at­or­i­al games and some of the math­em­at­ics be­hind them. In 2017 he also be­came the ini­tial donor to fund “Amer­ica Asks, Sci­ence An­swers”, a new pub­lic in­form­a­tion cam­paign by the Na­tion­al Academies. In 1979 El­wyn joined oth­er MSRI founders in a meet­ing which per­suaded UC Berke­ley Chan­cel­lor Al­bert Bowker to sup­port (verbally but not fin­an­cially) MSRI as an al­lied but in­de­pend­ent off-cam­pus en­tity, with its own board of gov­ernors, neither con­trolled nor over­seen by UC Berke­ley. Serving as Chair­man of the Board from 1994 to 1997, he hired the cur­rent MSRI dir­ect­or, Dav­id Eis­en­bud who wrote of El­wyn’s con­nec­tions to MSRI in his “Me­mori­am: El­wyn Ber­lekamp”. With his wife Jen­nifer, El­wyn sup­por­ted vari­ous char­it­able causes and in 2013 foun­ded the El­wyn and Jen­nifer Ber­lekamp Found­a­tion, a small private op­er­at­ing found­a­tion based in Oak­land to sup­port math and sci­ence out­reach and edu­ca­tion in gen­er­al and com­bin­at­or­i­al game the­ory in par­tic­u­lar.

Like oth­ers with Top Secret clear­ances in cryp­to­graphy, El­wyn re­frained from pub­lish­ing any pa­pers dir­ectly re­lat­ing to cryp­to­graphy, wheth­er they were clas­si­fied or not. We once vis­ited the Na­tion­al Se­cur­ity Agency (NSA) where I was able to see clas­si­fied re­ports he had au­thored. In the 1970s aca­dem­ic pa­pers on cryp­to­graphy star­ted to ap­pear in aca­dem­ic journ­als, arous­ing con­cerns at the NSA that this in­form­a­tion might be use­ful to U.S. ad­versar­ies. To ad­dress these con­cerns, the then Dir­ect­or of NSA in­vited El­wyn to meet­ings with cog­niz­ant aca­dem­ics. He later con­vened meet­ings at UC Berke­ley which led to a com­mis­sion of rel­ev­ant schol­arly so­ci­et­ies ad­dress­ing these con­cerns. Throughout his ca­reer El­wyn con­tinu­ously made sig­ni­fic­ant con­tri­bu­tions to re­search and teach­ing, de­veloped prac­tic­al ap­plic­a­tions as a suc­cess­ful en­tre­pren­eur, sup­por­ted edu­ca­tion in math­em­at­ics, and held lead­er­ship roles in aca­dem­ic so­ci­et­ies. He served on over 45 boards of vari­ous kinds. In 1973, he be­came one of a dozen fac­ulty co-founders of the Com­puter Sci­ence Di­vi­sion with­in UC Berke­ley’s De­part­ment of Elec­tric­al En­gin­eer­ing and Com­puter Sci­ence. His many stu­dents have in turn made sig­ni­fic­ant im­pacts in elec­tric­al en­gin­eer­ing and com­puter sci­ence. For ex­ample, one of his stu­dents, Ken Thompson, be­came the co-in­vent­or of the Unix op­er­at­ing sys­tem. Many oth­ers have be­come lead­ers in aca­demia and in­dustry. El­wyn served in many lead­er­ship roles at the Uni­versity of Cali­for­nia, IEEE, Na­tion­al Academy of Sci­ences, Na­tion­al Academy of En­gin­eer­ing, non­profit edu­ca­tion or­gan­iz­a­tions, and MSRI. El­wyn and I first met at MIT sixty years ago. Over the past few years we would meet for long lunches once every couple of months, shar­ing stor­ies and more of­ten dis­cuss­ing world events and so­cial is­sues. El­wyn cared a lot about edu­ca­tion and wor­ried about in­equal­it­ies in our so­ci­ety. It has been a priv­ilege to have had El­wyn as a col­league and friend.

• Com­puter His­tory Mu­seum
• MSRI: msri.org/web/msri/com­mu­nic­a­tions/el­wyn-ber­lekamp
• Wiki­pe­dia page: wiki­pe­dia.org/wiki/El­wyn­_Ber­lekamp
• Berke­ley News: “El­wyn Ber­lekamp, game the­or­ist and cod­ing pi­on­eer, dies at 78”
• Wall Street Journ­al: “Math Wiz­ard El­wyn Ber­lekamp Helped Bring Sharp Im­ages From Out­er Space”
• El­wyn Ber­lekamp’s home page (UC Berke­ley)
• Num­berphile: “How to Al­ways Win at Dots and Boxes”
• Num­berphile: “A fi­nal game with El­wyn Ber­lekamp (Amazons)”
• Amer­ic­an Go As­so­ci­ation: “El­wyn Ber­lekamp’s Coupon Go” (filmed at UC Berke­ley in 2006)