Meeting times: Tuesday and Thursday 12:30-1:45 CSI 2120 The goal of the course is to study several
recent research directions in coding theory. The course will cover the following
topics (at present the list is tentative). 1. Reed-Muller codes of the 2nd order and their subcodes.
Geometric view; algebraic view as of Z4-linear codes. Extensions of
finite rings (Galois rings). List decoding of Reed-Muller codes, of Kerdock
codes. 2. Isoperimetric theorems and their applications in coding theory 3
Instructor: Alexander
Barg
Course notes:
Topics in Coding
Theory
A unifying topic here is the phenomenon of measure concentration. We
begin with the classical work of Margulis on the phase transition phenomenon for
the connectivity problem of random graphs and then show how similar ideas help
to establish the existence of a threshold error probability for decoding of
codes on the binary symmetric channel and the Gaussian channel.
Delsarte’s theory of association schemes; Orthogonal polynomials and their
varied applications in coding theory, communication complexity, combinatorics.
Dirichlet kernel and its applications in coding (new proofs of the best known
upper bounds on codes). Uniform distribution: designs, orthogonal arrays.
Packing density of Rn: a proof by Cohn-Elkies and Yudin of
Levenshtein’s bound.
4. Use of codes in cryptography.
Wire-tap channel and generalized Hamming weights. Authentication codes.
Secret-sharing schemes. Codes with the identifying parent property,
fingerprinting codes.
5. Expander graphs and their codes.
Codes constructed on graphs with an expanding property. Estimates of the
distance, decoding.
Prerequisites: ENEE626 Error Correcting codes (working knowledge), basic undergraduate mathematics such as Algebra I, Linear Algebra, Combinatorics, Analysis.
Grade: Course in the form of lectures, student presentations, term project. A typical project will involve studying variations of the topics discussed in class and will go beyond review of the literature. Active participation by the students is expected. There will be no home assignments or exams.