Elwyn Berlekamp, game theorist and coding pioneer, dies at 78
His error-correcting codes allowed spacecraft to send beautiful images back to Earth
April 18, 2019
Elwyn Berlekamp in 2006. (Photo courtesy of David Eisenbud)
Elwyn Berlekamp, a UC Berkeley mathematician and game theorist whose error-correcting codes allowed spacecraft from Voyager to the Hubble Space Telescope to send accurate, detailed and beautiful images back to Earth, died April 9 at his home in Piedmont, California, from complications of pulmonary fibrosis.
A professor emeritus of mathematics and of electrical engineering and computer sciences, Berlekamp was 78.
Berlekamp was a “genius” in many areas, according to colleague Richard Karp, a UC Berkeley professor emeritus of electrical engineering and computer sciences and holder of computer science’s premier honor, the Turing Award.
“He was a brilliant person who was always effective in everything he tried to do, whether it was mathematics or game theory or consulting and investment. He had a curious and powerful mind,” said Karp, who was the first chair of UC Berkeley’s computer sciences division upon its creation and merger with electrical engineering in 1973. Berlekamp succeeded Karp as chair from 1975 to 1977.
Berlekamp came of age during the early years of the digital revolution and focused on a problem encountered whenever information is sent from one device to another: How do you account for lost bits of data? He developed algebraic algorithms for compressing images or other information in ways that allowed precise reconstruction, even if parts of the data stream were missing due to noise or faulty transmission.
When he felt that his error-correcting codes were not being implemented properly, he founded a company, Cyclotomics, to ensure that they were. The company’s bit-serial encoders and Berlekamp decoders became the NASA standard for space communications. They’re still operating on the Voyager I and II spacecraft, which were launched in 1977 and are now at the outer edges of our solar system.
The company employed error-correcting codes to develop numerous innovative electronic subsystems and custom integrated circuits that were used in military communications, optical disk memories, magnetic disk memories, floppy disk memories and compact disks, while the techniques were adapted for optically encoding digital sound tracks on movie film.
Cyclotomics’ sound encoding/decoding system was a prototype for Eastman Kodak’s Digital Sound System, which won an Academy Award for scientific and technical achievement in 1995, but was later supplanted by other techniques, including Dolby Sound. Kodak acquired Cyclotomics in 1985 and renamed it Kodak Berkeley Research.
Hedge fund
Berlekamp later branched out into cryptography and the financial market, where companies were beginning to use complex mathematics to predict stock performance, most notably in derivatives. In 1989, he bought controlling shares in a failing firm, Axcom, that had asked for his help with its algorithms. He rewrote them and turned the company around, making a 55% net return during its first year.
Berlekamp playing games with Richard Nowakowski in 2015 following a symposium on combinatorial games, his life-long passion. (Photo courtesy of David Eisenbud)
In 1990, he sold his interest in the company for six times the purchase price to mathematician and former Renaissance Technologies CEO James Simons, then returned to research at UC Berkeley. The company’s algorithms, with a continual series of enhancements and improvements, performed well for the remainder of the decade, laying the foundation for Renaissance’s Medallion Fund, which is the most successful hedge fund in the world.
Berlekamp founded his own hedge fund, Berkeley Quantitative, in 2008, focusing on trading in the futures markets, but it closed after two and a half years.
For the last three decades of his life, he focused on the theory of combinatorial games, the most simple example of which, Dots and Boxes, had fascinated him since first grade. He developed theories of the game that allowed him, or anyone, to always win.
His two-volume series, Winning Ways for Your Mathematical Plays (1982, Academic Press), written with John Conway and Richard Guy, delved into the math of Dots and Boxes and other popular games, including Amazons, a game played on a chess board with queens only. It was republished in 2001-2004 in four volumes.
“In these books, he manages to describe deep mathematics in a way that is really enjoyable to the reader,” Karp said. “He presents it more as a narrative and explains it with real precision, but in a way that is actually charming. He was a wonderful author as well.”
One of his passions was the Asian game of Go, which he analyzed with coauthor David Wolfe in the book Mathematical Go (1994, A. K. Peters Ltd.) — one of the rare books on Go to be translated from English into Japanese, rather than vice versa. He focused on Go’s endgame, said mathematician and colleague David Eisenbud, and once challenged a top Japanese Go master to a series of endgames selected by Berlekamp. He beat the Go master in seven straight games, playing both sides of the board — white and black.
“It was mathematics against intuition, and mathematics won,” said Eisenbud, director of the Mathematical Sciences Research Institute (MSRI). “It was an impressive demonstration of which he was very proud.”
While the mathematical analysis of games is still very popular, computers have taken the field in a different direction: they employ brute force or machine learning to beat Go and chess masters.
Mathematical Sciences Research Institute
From the 1970s on, Berlekamp was a strong supporter of MSRI, a non-profit mathematics think tank launched in 1982 and housed in a building on land leased from the university in the hills above the campus. He served as chairman of the board from 1994 to 1998, during which time Eisenbud was hired as director, in 1997, and spearheaded fundraising that proved critical to the long-term success of the institute.
His contributions to MSRI are honored by a Berlekamp Postdoctoral Fellowship, which was endowed in 2014 with more than $1 million in donations from friends, and a Berlekamp Garden created in 2006.
Berlekamp was born in Dover, Ohio, the son of a minister, on Sept. 6, 1940, and later moved with his family to northern Kentucky, where he graduated from Ft. Thomas Highlands High School in 1958. He attended the Massachusetts Institute of Technology, obtaining a B.S. and an M.S. in electrical engineering in 1962 and a Ph.D. in electrical engineering in 1964.
That same year, he was appointed an assistant professor of electrical engineering at Berkeley, but left in 1967 for Bell Telephone Laboratories, where he had interned as an undergraduate. While at Bell Labs, he wrote his seminal book, Algebraic Coding Theory (1968), which is considered the bible of the field. The well-known Berlekamp polynomial factoring algorithm was the first, and for many years the most efficient, technique for finding solutions of large polynomial equations created in fields like coding, and is still used in cryptography.
He returned to Berkeley in 1971 with a joint appointment in mathematics and electrical engineering, reduced his teaching appointment to part-time in 1982 to focus on his company, Cyclotomics, and retired in 2006.
“He was a brilliant person, caring father, accomplished juggler and he had a great sense of humor. He’ll not be forgotten,” said David Patterson, a professor emeritus of electrical engineering and computer sciences at Berkeley who is now a distinguished engineer at Google and a Turing Award winner.
Berlekamp and his wife, Jennifer, supported various charitable causes and in 2013 founded the Elwyn and Jennifer Berlekamp Foundation, a small private operating foundation based in Oakland to support math and science outreach and education, in general, and combinatorial game theory, in particular.
Berlekamp playing the game Amazons with Georg Menz in 2015. Menz was that year’s Berlekamp Postdoctoral Fellow at MSRI. (Photo courtesy of David Eisenbud)
Berlekamp was a member of the National Academy of Sciences and National Academy of Engineering and a fellow of the Institute of Electrical and Electronics Engineers (IEEE), the American Mathematical Society, the American Association for the Advancement of Science and the American Academy of Arts and Sciences. He received various honors, including the Centennial Medal, the Koji Kobayashi Computers and Communications Award and the R. W. Hamming Medal, all from IEEE, and was selected as Eta Kappa Nu’s “Outstanding Young Electrical Engineer” in 1971 and as a Putnam Fellow in 1961. He held more than a dozen patents, all of them now in the public domain.
He is survived by his wife, Jennifer; daughters Persis Berlekamp, an art historian at the University of Chicago, and Bronwen Berlekamp O’Wril of Portland, Maine; and son David of Oakland.
A memorial is planned within the coming months. For updates, check the MSRI website.