2009 Technical Reports (PDF 1.5MB)        2007 MSRI-UP        2008 MSRI-UP

Overview of the summer program

The MSRI-UP summer program is designed for undergraduate students who have completed two years of university-level mathematics courses and would like to conduct research in the mathematical sciences. The academic portion of the program will be led by John B. Little, Professor of Mathematics at College of the Holy Cross. Dr. Little has done research in many mathematical fields including computational algebra and coding theory and has extensive experience with directing
undergraduate research. Indeed, he has worked in Research Experience for Undergraduates (REUs) in both the U.S. and Puerto Rico.

During the summer, each of the 18 student participants will:

• participate in the mathematics research program under the direction of Dr. Little
• complete a research project done in collaboration with other MSRI-UP students
• give a presentation and write a technical report on his/her research project
• attend a series of colloquium talks given by leading researches in their fields
• attend workshops aimed at developing skills and techniques needed for research careers in the mathematical sciences and
• learn techniques that will maximize a student's likelihood of admissions to graduate programs as well as the likelihood of winning fellowships
• receive a $3000 stipend, lodging, meals and roundtrip travel to Berkeley, CA.

After the summer, each student will:

• have an opportunity to attend a national mathematics or science conference where students will present their research
• be part of a network of mentors that will provide continuous advice in the long term as the student makes progress in his/her studies
• be contacted regarding future research opportunities

The main objective of the MSRI-UP is to identify talented students, especially those from underrepresented groups, who are interested in mathematics and make available to them meaningful research opportunities, the necessary skills and knowledge to participate in successful collaborations, and a community of academic peers and mentors who can advise, encourage and support them through a successful graduate program.

The objective is designed to contribute significantly toward meeting the program goal of increasing the number of graduate degrees in the mathematical sciences, especially doctorates, earned by U.S. citizens and permanent residents by cultivating heretofore untapped mathematical talent within the U.S. Black, Hispanic/Latino and Native American communities.

Topic: Coding Theory

Prerequisite: A solid course in linear algebra and a course where a student develops skill in reading and constructing proofs.

Communication of information often takes place over noisy channels that can corrupt the messages sent over them. For reliability of communication, it is often desirable to encode the transmitted information in such a way that errors can be detected and/or corrected when they occur. Finding methods that achieve error control without introducing undue redundancy, and that admit efficient encoding and decoding, is the main goal of coding theory.

Consider a communications environment in which messages are divided into words or blocks of a fixed length, k, formed using a finite alphabet with q symbols. The simplest case (the one best adapted to electronic hardware) is an alphabet with two symbols, the binary digits 0, 1. Indeed, in the codes used for the transfer of digital information within computer systems, and for storing information on compact disks, or other media and retrieving it for use at a later time, q is either 2 or a power of 2. The alphabet with exactly two symbols can be identified with the finite field , but the theory is substantially the same if the alphabet is any finite field . In order to detect and/or correct errors when they occur, some redundancy must be built into the information that is transmitted over the channel. One possible approach is to make the encoded form of a message consist of blocks or n-tuples of length n>k over the same alphabet used for the message itself. Codes obtained in this way are called block codes of length n over the alphabet.

The summer will start with a quick (2 week) short course giving an introduction to the theory of block codes over and other finite fields including: the Hamming distance, the parameters n,k,d of codes and some elementary bounds (Gilbert-Varshamov, Hamming, Singleton, etc.) on the parameters, linear codes, generator and parity check matrices for encoding and syndrome decoding, some important examples such as Hamming and Golay codes, cyclic codes and associated polynomial algebra, general finite fields, Reed-Solomon and BCH codes, algebraic decoding algorithms.

The basic decoding method for Reed-Solomon codes (leading up to the Berlekamp-Massey algorithm) is designed to correct up to t=[(d-1)/2]=[(n-k)/2] errors in a received word. By results on the error-correcting capacity of a code in terms of its minimum distance, this restriction on the number of errors is necessary if we ask for a method that returns only one closest codeword for each received word. There has been a surge of interest in different algorithms for Reed-Solomon and other codes in recent years.

Starting with work of Sudan in the late 1990’s and followed by work of Guruswami & and Sudan and Roth & Ruckstein, a significant amount of work has been devoted to methods that produce a list of all codewords within some specified distance (possibly >t above) of the received word.

Projects

The bulk of the program will be devoted to work on the projects.

Important