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 (algebra), space (geometry), and change. It has no generally accepted definition.

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.

Life and education

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.

Dover, Ohio City in Ohio, United States

Dover is a city in Tuscarawas County, Ohio, United States, located approximately 68.75 miles S of Cleveland, and 2.60 miles NW of New Philadelphia. The largest nearby city outside Ohio is Pittsburgh, Pennsylvania, 77.21 miles away, almost directly east. The population of Dover was 12,286 at the 2010 census.

Massachusetts Institute of Technology University in Massachusetts

The Massachusetts Institute of Technology (MIT) is a private research university in Cambridge, Massachusetts. The Institute is a land-grant, sea-grant, and space-grant university, with an urban campus that extends more than a mile (1.6 km) alongside the Charles River. The Institute also encompasses a number of major off-campus facilities such as the MIT Lincoln Laboratory, the Bates Center, and the Haystack Observatory, as well as affiliated laboratories such as the Broad and Whitehead Institutes. 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. It has since played a key role in the development of many aspects of modern science, engineering, mathematics, and technology, and is widely known for its innovation and academic strength, making it one of the most prestigious institutions of higher learning in the world.

Electrical engineering Field of engineering that deals with electricity

Electrical engineering is a technical discipline concerned with the study, design and application of equipment, devices and systems which use electricity, electronics, and electromagnetism. It emerged as an identified activity in the latter half of the 19th century after commercialization of the electric telegraph, the telephone, and electrical power generation, distribution and use.

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

Piedmont, California City in California, United States

Piedmont is a small, mostly residential, semi-suburban city located in Alameda County, California, United States. Piedmont is completely surrounded by the city of Oakland. Its residential population was 10,667 at the 2010 census. The name comes after the region of Piedmont in Italy, and literally means foothill. Piedmont was incorporated in 1907, and was developed significantly in the 1920s and 1930s. The Piedmont Unified School District (PUSD) includes three elementary schools, one middle school, and two high schools.

Pulmonary fibrosis human disease

Pulmonary fibrosis is a respiratory disease in which scars are formed in the lung tissues, leading to serious breathing problems. Scar formation, the accumulation of excess fibrous connective tissue, leads to thickening of the walls, and causes reduced oxygen supply in the blood. A consequence is a perpetual shortness of breath.

Career

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] [4]

University of California, Berkeley Public university in California, USA

The University of California, Berkeley is a public research university in Berkeley, California. It was founded in 1868 and serves as the flagship campus of the ten campuses of the University of California. Berkeley has since grown to instruct over 40,000 students in approximately 350 undergraduate and graduate degree programs covering numerous disciplines.

Bell Labs Research and scientific development company

Nokia Bell Labs is an industrial research and scientific development company owned by Finnish company Nokia. Its headquarters are located in Murray Hill, New Jersey. Other laboratories are located around the world. Bell Labs has its origins in the complex past of the Bell System.

He was a member of the National Academy of Engineering (1977) [5] and the National Academy of Sciences (1999). [6] He was elected a Fellow of the American Academy of Arts and Sciences in 1996, [7] and became a fellow of the American Mathematical Society in 2012. [8] In 1991, he received the IEEE Richard W. Hamming Medal, [9] 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. [10] He was one of the founders of Gathering 4 Gardner and was on its board for many years. [11] In the mid-1980s, he was president of Cyclotomics, Inc., a corporation that developed error-correcting code technology. [1]

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.

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

Berlekamp and Martin Gardner

Berlekamp was a close friend of Scientific American columnist Martin Gardner and was an important member of the gifted and diverse group of people that Gardner nurtured and acted as a conduit for; people who inspired Gardner and who were in turn inspired by him. [13] Berlekamp teamed up with John Horton Conway and Richard K. Guy, two other close associates of Gardner, to co-author the book Winning Ways for your Mathematical Plays leading to his recognition as one of the founders of combinatorial game theory. [14] The dedication of their book says, "To Martin Gardner, who has brought more mathematics to more millions than anyone else." [15]

Berlekamp and Gardner both had great love for and were strong advocates of recreational mathematics. [14] Conferences called Gathering 4 Gardner (G4G) are held every two years to celebrate the Gardner legacy. [13] Berlekamp was one of the founders of G4G and was on its board of directors for many years. [16]

Selected publications

Related Research Articles

John Horton Conway English 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 John von Neumann Professor Emeritus.

Martin Gardner recreational mathematician and philosopher

Martin Gardner was an American popular mathematics and popular science writer, with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literature—especially the writings of Lewis Carroll, L. Frank Baum, and G. K. Chesterton. He is recognized as a leading authority on Lewis Carroll. The Annotated Alice, which incorporated the text of Carroll's two Alice books, was his most successful work and sold over a million copies. He had a lifelong interest in magic and illusion and was regarded as one of the most important magicians of the twentieth century. He was considered the doyen of American puzzlers. He was a prolific and versatile author, publishing more than 100 books.

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.

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.

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.

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.

The Black Path Game is a two-player board game described and analysed in Winning Ways for your Mathematical Plays. It was invented by Larry Black in 1960.

Richard K. Guy British mathematician

Richard Kenneth Guy is a British mathematician and 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.

Solomon W. Golomb American mathematician

Solomon Wolf Golomb was an American mathematician, engineer, and professor of electrical engineering at the University of Southern California, best known for his works on mathematical games. Most notably, he invented Cheskers in 1948 and coined the name. He also fully described polyominoes and pentominoes in 1953. He specialized in problems of combinatorial analysis, number theory, coding theory, and communications. His game of pentomino inspired Tetris.

Dodgem

Dodgem is a simple abstract strategy game invented by Colin Vout in 1972 while he was a mathematics student at the University of Cambridge as 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.

James Lee Massey was an information theorist and cryptographer, Professor Emeritus of Digital Technology at ETH Zurich. His notable work includes the application of the Berlekamp–Massey algorithm to linear codes, the design of the block ciphers IDEA and SAFER, and the Massey-Omura cryptosystem.

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.

Treblecross is a degenerate tic-tac toe variant. The game is an octal game, played on a one-dimensional board and both players play using the same piece. Each player on their turn plays a piece in an unoccupied space. The game is won if a player on their turn creates a line of three pieces in a row.

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 Elwyn 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. Elwyn Berlekamp, game theorist and coding pioneer, dies at 78 Berkeley News, By Robert Sanders, April 18, 2019
  4. Contributors, IEEE Transactions on Information Theory20, #3 (May 1974), p. 408.
  5. "NAE Members Directory – Dr. Elwyn R. Berlekamp". NAE . Retrieved June 16, 2011.
  6. "NAS Membership Directory". NAS . Retrieved June 16, 2011. Search with "Last Name" is Berlekamp.
  7. "Book of Members, 1780–2010: Chapter B" (PDF). American Academy of Arts and Sciences. Retrieved June 16, 2011.
  8. List of Fellows of the American Mathematical Society, retrieved 2012-11-10.
  9. "IEEE Richard W. Hamming Medal Recipients" (PDF). IEEE . Retrieved May 29, 2011.
  10. "Golden Jubilee Awards for Technological Innovation". IEEE Information Theory Society . Retrieved July 14, 2011.
  11. About Gathering 4 Gardner Foundation Archived 2016-05-07 at the Wayback Machine
  12. Financial Engineering, Elwyn Berlekamp's Home Page. Accessed on line October 30, 2007.
  13. 1 2 Elwyn Berlekamp Tribute by Gathering 4 Gardner on April 17, 2019
  14. 1 2 The Mathematical Legacy of Martin Gardner by Elwyn Berlekamp, Society for Industrial and Applied Mathematics (SIAM), September 2, 2014: Partly because of what I had read about them in Martin Gardner’s columns, I was appropriately awestruck in the 1960s when I first met Sol Golomb and then Richard Guy, each of whom had a large influence on my subsequent work. In 1969 Richard introduced me to John Horton Conway, and the three of us immediately began collaborating on a book that eventually became Winning Ways for Your Mathematical Plays. In the 1970s, I joined Conway in some of his many visits to Gardner’s home on Euclid Avenue, in Hastings-on-Hudson, New York. Gardner soon became an enthusiastic advocate of our book project, and he previewed various snippets of it in his Scientific American columns.
  15. Berlekamp, Elwyn R., John H. Conway, and Richard K. Guy (1982). Winning Ways for your Mathematical Plays Academic Press, ISBN   0120911507.
  16. History of the Gathering Gathering 4 Gardner
  17. 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.
  18. 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.