In Memoriam: Elwyn Berlekamp
Tribute to Elwyn Berlekamp, who passed away on April 9, 2019. Jim Omura writes about Elwyn's broad and substantial contributions to information theory, coding theory, and game theory
Jun 12, 2019
Berlekamp

Elwyn Berlekamp passed away on April 9, 2019 in Berkeley, California. He was a brilliant mathematician and engineer who did groundbreaking research in Information Theory and Combinatorial Game Theory. He was also a successful entrepreneur, helped create a highly profitable quantitatively managed fund, served in leadership roles for academic societies, and was a generous supporter of STEM education and mathematics research. Elwyn is survived by his wife, Jennifer; daughters Persis, an art historian at the University of Chicago, and Bronwen Berlekamp O’Wril of Portland, Maine; and son David of Oakland.

Early Years

Elwyn Berlekamp was born on September 6, 1940 in Dover, Ohio. His family moved to Northern Kentucky, where Elwyn was class president at Highland High School. In 1958 he and I entered MIT as freshmen. I first met Elwyn in our sophomore year when we played together on the East Campus intramural football team.

Elwyn was the smartest student I met at MIT. He took extra courses during his undergraduate years, completing his BS and MS degrees in 4 years and his PhD two years later, all at MIT. In addition, he taught himself Russian and together with other undergraduate students developed the first chess-playing software program, which is featured in the Computer History Museum in Mountain View, California. Although an Electrical Engineering student, he was among five winners of the national Putnam Mathematics competition in December 1961. His PhD thesis, Block Coding with Noiseless Feedback, spawned several publications. One key idea was to recast the problem as an asymmetric combinatorial game between the Coder and the Noisemaker and then to find asymptotically optimum strategies for playing that game. This was followed by his groundbreaking research work in Information Theory, Mathematics, and Combinatorial Game Theory. Less known is his mostly classified consulting work on cryptographic research for the Institute for Defense Analysis (IDA) in Princeton, New Jersey.

Research in Information Theory

In addition to his long career at the University of California Berkeley, Elwyn worked for short periods at Bell Labs, the Jet Propulsion Laboratory (JPL) and IDA.

He invented a series of algorithms and related implementations which made powerful error-correcting codes useful in many applications. Best-known among these results was his algorithm to factor polynomials over finite fields and the Berlekamp-Massey algorithm to find linear recursions in long data streams. These were published in his 1968 book, Algebraic Coding Theory . Another major new result in that book was the enumeration of the number of information bits in long binary BCH codes. This book won the IEEE Information Theory Group's annual best research paper award. The applicability of some of these algorithms to problems in cryptography attracted the attention of the National Security Agency (NSA), who in 1967-1968 recruited Elwyn to become a consultant to their research group at IDA.

Entrepreneur

Some believed that Elwyn's algorithms were impractical. Without angel investors or venture capital, he founded Cyclotomics to develop commercial implementations, starting with the world's foremost Galois Field computer which shattered the then-prevalent myth that powerful high-speed algebraic error-correction was not feasible. Elwyn's Galois Field computer is now in the Computer History Museum.

When I met him during this period, I was amazed to see Elwyn programming an early microprocessor and designing integrated circuits. This work led to Elwyn becoming the youngest member of the National Academy of Engineering in 1977.

Cyclotomics bootstrapped its growth with profitable sales, and eventually grew to a peak of 40 people. It worked with NASA to design and build the error-correction decoders for the downlink of the Hubble Space Telescope. Beyond communications, Cyclotomics also pioneered applications of algebraic error-correction technology to several data storage technologies, including magnetic tapes, magnetic discs, and optical discs. By the mid-1980s, there were over 40 US companies trying to develop read-write optical memories. Cyclotomics developed controllers for several of them. The biggest of these companies was Eastman Kodak which acquired Cyclotomics in 1985.

In 1984 Cyclotomics spun off its consulting contracts in cryptography to a new startup, which became known as Cylink and which I co-founded with Elwyn and others. Cylink obtained angel funding from a group formed by Jim Simons, whom Elwyn had met at an IDA interview in 1967. In 1996 Cylink went public on the NASDAQ stock exchange.

The Medallion Quant Fund

Simons had started a hedge fund management firm, which became Renaissance Technologies in 1982. Six years later Renaissance established the Medallion quant fund using Leonard Baum's mathematical models, which were improved by pioneering algebraist James Ax to explore correlations from which they could profit. Around 1989 this fund, then called Axcom with Ax as CEO, was not doing well. Having met again as members of Cylink's board of directors, Simons turned to Elwyn to run Medallion from Berkeley. Elwyn bought out most of Ax's stake in Axcom and became its CEO. Over a six-month period, he worked with Simons, Sandor Straus, and consultant Henry Laufer to overhaul Medallion's trading system. In 1990 Elwyn led Medallion to a 55.9% gain, net of fees, and then returned to teaching at Berkeley after selling out his Axcom shares to Simons at six times the price he had paid 16 months earlier. Straus took the reins of Medallion's revamped trading system, and Medallion returned 39.4% in 1991, 34% in 1992 and 39.1% in 1993. They continued hiring mathematicians, engineers, and scientists and expanded into trading stocks as well as futures. The Medallion fund became the most successful hedge fund ever, averaging a 71.8% annual return, before fees, from 1994 through mid-2014. It made Simons the leading fund manager on Wall Street. 

In the early 2000s, four new partners and Elwyn launched another quantitatively managed fund, called Berkeley Quantitative (BQ). After two years of development and studies, it accepted money from outside investors and began trading. As more investors entered, the fund size grew. Net performance reached 17%, and the fund size reached $250 million about 1.5 years after trading had begun. But the next couple of months saw unfriendly market conditions aggravated by some internal organizational problems and BQ was closed down after paying off its debts. The initial investors realized a net return of about 2% after 3 years. Elwyn felt that BQ was not a success, but it did much better than the wipe-outs experienced by many startups at that time.

Combinatorial Game Theory

Elwyn's fascination with mathematical games began when he learned to play Dots-and-Boxes in the first grade. Years later he discovered several mathematical theorems that underlie this game and others. In mathematics, his best-known work was in Combinatorial Game Theory, partly disseminated in his four-volume work Winning Ways with John H. Conway and Richard Guy. According to Martin Gardner, author of the extremely popular Mathematical Games column in Scientific American from 1957 to 1982, Winning Ways was the "greatest contribution of the 20th century to the burgeoning field of recreational mathematics. No other work has been so packed with completely new and significant material, or presented with so much wit, depth, and clarity." These books also became the foundation of a less-recreational subject called Combinatorial Game Theory. It was officially accepted by Math Reviews (now MathSciNet) as a new branch of mathematics and attracted the interest and contributions of many mathematicians and computer scientists.

Another of Elwyn's accomplishments in Combinatorial Game Theory was his analysis of positions in the endgame of Go. With David Wolfe, he published the book Mathematical Go. He demonstrated the effectiveness of his theory by setting up a plausible endgame position from which he beat one of the Japanese champions of the game, after which he set up the same position, reversed the board, and beat the master a second time. He also invented a variation of the game called Coupon Go, which is closer to elegant mathematical theories. This attracted the attention of both mathematicians and several world-class professional Go players.

Contributions to STEM education and the Mathematical Sciences Research Institute (MSRI)

Elwyn’s father was a minister, and one sees the father’s influence on the son in a strong and consistent ideal of service to the greater good.

Elwyn was active in the popularization of Science, Technology, Engineering, and Mathematics (STEM), directed both at K-12 education and at adults. He served on the governing boards of each of the two foremost private schools in Oakland, California, College Preparatory School and Head-Royce. He also directed his efforts towards extra-curricular education. In the late 1970s, he helped finance the start of the Berkeley Math Circle for junior high school students who met in a classroom one evening per week to share and enjoy solving math or logic problems not covered in their school curricula. He felt that one key to the success of such efforts was to eradicate (or at least blur) the line many students imagine between "real" mathematics/engineering and "recreational mathematics."

In 1979 Elwyn joined other MSRI founders in a meeting that persuaded UC Berkeley Chancellor Albert Bowker to support (verbally but not financially) MSRI as an allied but independent off-campus entity, with its own board of governors, neither controlled nor overseen by UC Berkeley. Serving as Chairman of the Board from 1994 to 1997, Elwyn hired the current MSRI director, David Eisenbud who wrote of Elwyn's connections to MSRI in his Memoriam: Elwyn Berlekamp.

Starting in 2015 he devoted much of his time to the preparation of short introductory videos aimed at getting more junior high school students interested in combinatorial games and some of the mathematics behind them. In 2017 he also became the initial donor to fund "America Asks, Science Answers”, a new public information campaign by the National Academies.

With his wife Jennifer, Elwyn supported various charitable causes and in 2013 founded the Elwyn and Jennifer Berlekamp Foundation, a small private foundation based in Oakland to support math and science outreach and education in general and Combinatorial Game Theory in particular.

In Closing

Like others with Top Secret clearances in cryptography, Elwyn refrained from publishing any papers directly relating to cryptography, whether they were classified or not. We once visited the National Security Agency (NSA) where I was able to see classified reports he had authored. In the 1970s academic papers on cryptography started to appear in academic journals, arousing concerns at the NSA that this information might be useful to U.S. adversaries. To address these concerns, the Director of NSA invited Elwyn to meetings with leading academics. Elwyn later convened similar meetings at UC Berkeley which led to a commission of relevant scholarly societies addressing these concerns.

Throughout his career Elwyn continuously made significant contributions to research and teaching, developed practical applications as a successful entrepreneur, supported education in mathematics, and held leadership roles in academic societies. He served on over 45 boards of various kinds. In 1973, he became one of a dozen faculty co-founders of the Computer Science Division within UC Berkeley's Department of Electrical Engineering and Computer Science. His many students have in turn made significant impacts in electrical engineering and computer science. For example, one of his students, Ken Thompson, became the co-inventor of the Unix operating system. Many others have become leaders in academia and industry. Elwyn served in numerous leadership roles at the University of California, IEEE, the National Academy of Sciences, the National Academy of Engineering, non-profit educational organizations, and MSRI.

Elwyn 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, sharing stories and often discussing world events and social issues. Elwyn cared a lot about education and worried about inequalities in our society. It has been a privilege to have had Elwyn as a colleague and friend.

Additional Information about the Life and Legacy of Elwyn Berlekamp

 

—  Jim Omura

Recent news