 |
Center for Nonlinear Studies |
Matroid theory is a study of a notion of independence that can be abstracted from the usual independence in linear algebra, as well as from trees and forests in graph theory. It is only natural to expect matroid > theory to have applications to the theory of error-correcting codes, as > matrices over finite fields are objects of fundamental importance in both these theories. An early application can be found in the work of Greene (1976) who (re-)derived the MacWilliams identities as special cases of an identity for the Tutte polynomial of a matroid. More recently, matroid methods have found applications in the study of graphical models for codes, and in the analysis of decoding methods such as the sum-product algorithm,and linear-programming decoding. In this tutorial-style talk, we will attempt to give an overview of the applications of matroid methods to coding theory. Among the topics covered will be the use of code/matroid decomposition techniques, and the notion of treewidth of graphs and matroids, in the analysis of graphical models and decoding algorithms for linear codes.
Host: Misha Chertkov, chertkov@lanl.gov, 665-8119