Computer Science/Discrete Mathematics Seminar I

This subject began in the late 1940s with the opus of Shannon [1948] and the short papers of Hamming [1950] and Golay [1949], followed a decade later by the powerful constructions of Bose-Chaudhuri-Hocquenghem and Reed-Solomon. A variety of techniques, some general, and some very specific, led to a large collection of results on how well code points can be distributed subject to various boundary constraints. The decoding problem motivated the invention of several algorithms, some of which are now used to address a wider variety of problems, such as factoring polynomials. In this talk, I will summarize and review some of the salient results of the latter half of the 20th century. I will also mention some easily-stated problems which remain unsolved.