Here are some of the things he worked on:
1) Factoring Polynomials over large finite fields (See here from 1970)
I quote the abstract
This paper reviews some of the known algorithms for factoring polynomials over finite fields and presents a new deterministic procedure for reducing the problem of factoring an arbitrary polynomial over the Galois field GP(pm) to the problem of finding roots in GF(p) of certain other polynomials over GP(p). The amount of computation and the storage space required by these algorithms are algebraic in both the degree of the polynomial to be factored and the log of the order of the field.
Certain observations on the application of these methods to factorization of polynomials over the rational integers are also included.I think he meant what we would call polynomial time when he says algebraic.
2) Combinatorial Games. He co-wrote the classic Winning Ways For your Mathematical Plays with John Conway and Richard Guy. These books are like NIM on steroids. They are FUN and have some serious math in them. (My blog system thinks Combinatorial is not a word. It is wrong)
3) Combinatorial Games. He was very interested in Go via Combinatorial Games. I have an article (alas, not online) by him entitled Introductory Overview of Mathematical Go Endgames. There has been further work on this that is on the web, see here. I wonder what ERB would think of the ALPHAGO program.
4) Berlekamp-Massey Algorithm finds the shortest linear feedback shift register for a given binary output sequence.
5) Berlekamp-Welch Algorithm efficiently corrects errors in Reed-Solomon codes. (Berlekamp also wrote a book on Algebraic Coding Theory.)
6) I didn't know about his work in finance until I began writing this, but the following quote from Wikipedia is impressive
In 1989, Berlekamp purchased the largest interest in a trading company named Axcom Trading Advisors. After the firm's futures trading algorithms were rewritten, Axcom's Medallion Fund had a return (in 1990) of 55%, net of all management fees and transaction costs. The fund has subsequently continued to realize annualized returns exceeding 30% under management by James Harris Simons and his Renaissance Technologies Corporation.
It could be mentioned that ERB was a Putnam Fellow in 1961, though he was studying electrical engineering and not math. He also did his PhD in EE (though at that time this may have been some sort of applied math) and later had an interesting career twist that attracted him to math proper.
ReplyDeleteGood summary but not much is mentioned about having had
ReplyDeletean amazing quadruple of "advisors" for his PhD.
To my surprise, Fano wasn't that involved ...
Survived by just one of his academic "parents"-- Robert G. Gallager (who is still with the Institute).
Equally interesting, the actual problem for his PhD originated by Claude Shannon.
Anecdotal: I was, for a brief period of time, a member of the Berkeley Go Club. Elwyn was also a (well-established) member, ranked around 1-dan (I was 6-kyu). But you would take your life in your hands to play with Elwyn -- he had written a lot of the mathematical theory of the Go endgame, and was very good at it, but kept trying to compute the surreal value of mid-game board positions. Which meant that it took him forever to make a move and his games generally lasted 4+ hours. Very friendly though, and if you were to play a game with him (with a good book at hand), you'd probably learn a lot.
ReplyDeleteVery sad news. I had the privilege of hearing him speak a few times in the 1980s. Of the great generation of coding theorists, Golomb, Reed, Berlekamp are no longer with us. McEliece is not well. Lloyd Welch is a bit younger, so is Sloane...
ReplyDelete... I forgot to include Massey, who passed away couple of years ago.
ReplyDeleteI was also a member of the Berkeley Go Club. I don't think Elwyn was ever 1-dan, but he was very fun to play. He usually talked to himself constantly as he was planning his moves, and his play would slow down as he approached the endgame and transitioned from intuition to combinatorial game theory calculations (also the talking would grow in complexity).
ReplyDelete