Elwyn Berlekamp

Last updated
Elwyn Berlekamp
Elwyn R Berlekamp 2005.jpg
Berlekamp in 2005
Born
Elwyn Ralph Berlekamp

(1940-09-06)September 6, 1940
DiedApril 9, 2019(2019-04-09) (aged 78)
NationalityAmerican
Alma mater Massachusetts Institute of Technology
Known for Berlekamp's algorithm, Berlekamp–Welch algorithm, Berlekamp–Massey algorithm, Coupon Go
Awards IEEE Richard W. Hamming Medal (1991)
Claude E. Shannon Award (1993)
Scientific career
Fields Information theory, Coding theory, Combinatorial game theory
Institutions University of California, Berkeley
Doctoral advisor Robert G. Gallager
Doctoral students Julia Kempe
Other notable students Ken Thompson

Elwyn Ralph Berlekamp (September 6, 1940 – April 9, 2019) was an American mathematician known for his work in computer science, coding theory and combinatorial game theory. He was a professor emeritus of mathematics and EECS at the University of California, Berkeley. [1] [2]

Coding theory study of the properties of codes and their fitness for a specific application

Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.

Combinatorial game theory branch of game theory about two-player sequential games with perfect information

Combinatorial game theory (CGT) is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position in which the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

Mathematics Field of study concerning quantity, patterns and change

Mathematics includes the study of such topics as quantity, structure, space, and change.

Contents

Berlekamp was the inventor of an algorithm to factor polynomials, and was one of the inventors of the Berlekamp–Welch algorithm and the Berlekamp–Massey algorithms, which are used to implement Reed–Solomon error correction.

The Berlekamp–Welch algorithm, also known as the Welch–Berlekamp algorithm, is named for Elwyn R. Berlekamp and Lloyd R. Welch. This is a decoder algorithm that efficiently corrects errors in Reed–Solomon codes for an RS(n, k), code based on the Reed Solomon original view where a message is used as coefficients of a polynomial or used with Lagrange interpolation to generate the polynomial of degree < k for inputs and then is applied to to create an encoded codeword .

The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear feedback shift register (LFSR) for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field. The field requirement means that the Berlekamp–Massey algorithm requires all non-zero elements to have a multiplicative inverse. Reeds and Sloane offer an extension to handle a ring.

Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960. They have many applications, the most prominent of which include consumer technologies such as CDs, DVDs, Blu-ray Discs, QR Codes, data transmission technologies such as DSL and WiMAX, broadcast systems such as satellite communications, DVB and ATSC, and storage systems such as RAID 6.

Berlekamp had also been active in money management. In 1986, he began information-theoretic studies of commodity and financial futures.

Money management is the process of expense tracking, investing, budgeting, banking and evaluating taxes of ones money which is also called investment management.

Biography

Berlekamp was born in Dover, Ohio. His family moved to Northern Kentucky, where Berlekamp graduated from Ft. Thomas Highlands high school in Ft. Thomas, Campbell county, Kentucky. While an undergraduate at the Massachusetts Institute of Technology (MIT), he was a Putnam Fellow in 1961. He completed his bachelor's and master's degrees in electrical engineering in 1962. Continuing his studies at MIT, he finished his Ph.D. in electrical engineering in 1964; his advisors were Robert G. Gallager, Peter Elias, Claude Shannon, and John Wozencraft. Berlekamp taught electrical engineering at the University of California, Berkeley from 1964 until 1966, when he became a mathematics researcher at Bell Labs. In 1971, Berlekamp returned to Berkeley as professor of mathematics and EECS, where he served as the advisor for over twenty doctoral students. [1] [2] [3]

Dover, Ohio City in Ohio, United States

Dover is a city in Tuscarawas County, Ohio, United States approximately 3 mi (4 km) northwest of New Philadelphia. The population was 12,210 at the 2000 census.

Massachusetts Institute of Technology University in Massachusetts

The Massachusetts Institute of Technology (MIT) is a private research university in Cambridge, Massachusetts. Founded in 1861 in response to the increasing industrialization of the United States, MIT adopted a European polytechnic university model and stressed laboratory instruction in applied science and engineering. The Institute is a land-grant, sea-grant, and space-grant university, with a campus that extends more than a mile alongside the Charles River. Its influence in the physical sciences, engineering, and architecture, and more recently in biology, economics, linguistics, management, and social science and art, has made it one of the most prestigious universities in the world. MIT is often ranked among the world's top universities.

Electrical engineering field of engineering that deals with electricity

Electrical engineering is a professional engineering discipline that generally deals with the study and application of electricity, electronics, and electromagnetism. This field first became an identifiable occupation in the later half of the 19th century after commercialization of the electric telegraph, the telephone, and electric power distribution and use. Subsequently, broadcasting and recording media made electronics part of daily life. The invention of the transistor, and later the integrated circuit, brought down the cost of electronics to the point they can be used in almost any household object.

He was a member of the National Academy of Engineering (1977) [4] and the National Academy of Sciences (1999). [5] He was elected a Fellow of the American Academy of Arts and Sciences in 1996, [6] and became a fellow of the American Mathematical Society in 2012. [7] In 1991, he received the IEEE Richard W. Hamming Medal, [8] and in 1993, the Claude E. Shannon Award. In 1998, he received a Golden Jubilee Award for Technological Innovation from the IEEE Information Theory Society. [9] He was one of the founders of Gathering 4 Gardner and was on its board for many years. [10] In the mid-1980s, he was president of Cyclotomics, Inc., a corporation that developed error-correcting code technology. [1]

The National Academy of Engineering (NAE) is an American nonprofit, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Sciences (NAS), the National Academy of Medicine, and the National Research Council.

American Academy of Arts and Sciences United States honorary society and center for independent policy research

The American Academy of Arts and Sciences is one of the oldest learned societies in the United States. Founded in 1780, the Academy is dedicated to honoring excellence and leadership, working across disciplines and divides, and advancing the common good.

American Mathematical Society association of professional mathematicians

The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, advocacy and other programs.

He co-authored the book Winning Ways for your Mathematical Plays with John Horton Conway and Richard K. Guy, leading to his recognition as one of the founders of combinatorial game theory. He has studied various games, including dots and boxes, Fox and Geese, and, especially, Go. Berlekamp and co-author David Wolfe describe methods for analyzing certain classes of Go endgames in the book Mathematical Go.

Winning Ways for your Mathematical Plays by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy is a compendium of information on mathematical games. It was first published in 1982 in two volumes.

John Horton Conway British mathematician

John Horton Conway is an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He has also contributed to many branches of recreational mathematics, notably the invention of the cellular automaton called the Game of Life. Conway spent the first half of his long career at the University of Cambridge, in England, and the second half at Princeton University in New Jersey, where he now holds the title Professor Emeritus.

Richard K. Guy British mathematician

Richard Kenneth Guy is a British mathematician, professor emeritus in the Department of Mathematics at the University of Calgary. He is known for his work in number theory, geometry, recreational mathematics, combinatorics, and graph theory. He is best known for co-authorship of Winning Ways for your Mathematical Plays and authorship of Unsolved Problems in Number Theory. He has also published over 300 papers. Guy proposed the partially tongue-in-cheek "Strong Law of Small Numbers," which says there are not enough small integers available for the many tasks assigned to them – thus explaining many coincidences and patterns found among numerous cultures. For this paper he received the MAA Lester R. Ford Award.

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. [11]

Berlekamp had two daughters and a son with his wife Jennifer. He lived in Piedmont, California. He died in April 2019 at the age of 78. [12]

Selected publications

Related Research Articles

In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first. The game is played until a terminal position is reached. A terminal position is one from which no moves are possible. Then one of the players is declared the winner and the other the loser. Furthermore, impartial games are played with perfect information and no chance moves, meaning all information about the game and operations for both players are visible to both players.

Misere, misère, bettel, betl, beddl or bettler is a bid in various card games, and the player who bids misere undertakes to win no tricks or as few as possible, usually at no trump, in the round to be played. This does not allow sufficient variety to constitute a game in its own right, but it is the basis of such trick-avoidance games as Hearts, and provides an optional contract for most games involving an auction.

In combinatorial game theory, a game is partisan if it is not impartial. That is, some moves are available to one player and not to the other.

Neil Sloane British mathematician

Neil James Alexander Sloane is a British-American mathematician. His major contributions are in the fields of combinatorics, error-correcting codes, and sphere packing. Sloane is best known for being the creator and maintainer of the On-Line Encyclopedia of Integer Sequences (OEIS).

Robert G. Gallager American electrical engineer

Robert Gray Gallager is an American electrical engineer known for his work on information theory and communications networks. He was elected an IEEE Fellow in 1968, a member of the National Academy of Engineering (NAE) in 1979, a member of the National Academy of Sciences (NAS) in 1992, a Fellow of the American Academy of Arts and Sciences (AAAS) in 1999. He received the Claude E. Shannon Award from the IEEE Information Theory Society in 1983. He also received the IEEE Centennial Medal in 1984, the IEEE Medal of Honor in 1990 "For fundamental contributions to communications coding techniques", the Marconi Prize in 2003, and a Dijkstra Prize in 2004, among other honors. For most of his career he was a professor of electrical engineering and computer science at the Massachusetts Institute of Technology.

Col is a pencil and paper game, specifically a map-coloring game, involving the shading of areas in a line drawing according to the rules of Graph coloring. With each move, the graph must remain proper, and a player who cannot make a legal move loses. The game was described and analysed by John Conway, who attributed it to Colin Vout, in On Numbers and Games.

Mac Elwyn Van Valkenburg was an American electrical engineer and university professor. He wrote seven textbooks and numerous scientific publications.

Dodgem

Dodgem is a simple abstract strategy game invented by Colin Vout in 1972 while a mathematics student at the University of Cambridge and described in the book Winning Ways. It is played on an n×n board with n-1 cars for each player—two cars each on a 3×3 board is enough for an interesting game, but larger sizes are also possible.

Lloyd Richard Welch is an American information theorist and applied mathematician, and co-inventor of the Baum–Welch algorithm and the Berlekamp–Welch algorithm, also known as the Welch–Berlekamp algorithm.

John Stillwell Australian mathematician

John Colin Stillwell is an Australian mathematician on the faculties of the University of San Francisco and Monash University.

The combinatorial game Toads and Frogs is a partisan game invented by Richard Guy. This mathematical game was used as an introductory game in the book Winning Ways for your Mathematical Plays.

In mathematics, tiny and miny are operators that yield infinitesimal values when applied to numbers in combinatorial game theory. Given a positive number G, tiny G is equal to {0||0|-G} for any game G, whereas miny G is tiny G's negative, or {G|0||0}.

In combinatorial game theory, a branch of mathematics, a hot game is one in which each player can improve their position by making the next move.

David Wolfe is a mathematician and amateur Go player.

Blockbusting is a solved combinatorial game introduced in 1987 by Elwyn Berlekamp illustrating a generalisation of overheating.

In combinatorial game theory, cooling, heating, and overheating are operations on hot games to make them more amenable to the traditional methods of the theory, which was originally devised for cold games in which the winner is the last player to have a legal move. Overheating was generalised by Berlekamp for the analysis of Blockbusting. Chilling and warming are variants used in the analysis of the endgame of Go.

References

  1. 1 2 3 Contributors, IEEE Transactions on Information Theory42, #3 (May 1996), p. 1048. DOI 10.1109/TIT.1996.490574.
  2. 1 2 Elwyn Berlekamp, listing at the Department of Mathematics, University of California, Berkeley.
  3. Contributors, IEEE Transactions on Information Theory20, #3 (May 1974), p. 408.
  4. "NAE Members Directory – Dr. Elwyn R. Berlekamp". NAE . Retrieved June 16, 2011.
  5. "NAS Membership Directory". NAS . Retrieved June 16, 2011. Search with "Last Name" is Berlekamp.
  6. "Book of Members, 1780–2010: Chapter B" (PDF). American Academy of Arts and Sciences. Retrieved June 16, 2011.
  7. List of Fellows of the American Mathematical Society, retrieved 2012-11-10.
  8. "IEEE Richard W. Hamming Medal Recipients" (PDF). IEEE . Retrieved May 29, 2011.
  9. "Golden Jubilee Awards for Technological Innovation". IEEE Information Theory Society . Retrieved July 14, 2011.
  10. About Gathering 4 Gardner Foundation Archived 2016-05-07 at the Wayback Machine
  11. Financial Engineering, Elwyn Berlekamp's Home Page. Accessed on line October 30, 2007.
  12. Ludus: Elwyn Berlekamp death notice (in Portuguese)
  13. Golomb, Solomon (1983). "Review: Winning ways for your mathematical plays, by E. R. Berlekamp, J. H. Conway, and R. K. Guy". Bull. Amer. Math. Soc. (N.S.). 8 (1): 108–111. doi:10.1090/s0273-0979-1983-15098-x.
  14. Guy, Richard K.; Nowakowski, Richard J. (1995). "Review: Mathematical Go: Chilling gets the last point, by Elwyn Berlekamp and David Wolfe" (PDF). Bull. Amer. Math. Soc. (N.S.). 32 (4): 437–441. doi:10.1090/S0273-0979-1995-00601-4.