A graphical realization of a linear code C consists of an assignment of the coordinates of C to the vertices of a graph, along with a specification of linear state spaces and linear local constraint codes to be associated with the edges and vertices, respectively, of the graph. Special cases of such realizations are trellises, Tanner graphs, and indeed any factor graph. A graphical realization of C specifies an associated sum-product decoding algorithm for C. The computational complexity of the associated sum-product algorithm is largely determined by the dimensions of the local constraint codes in the realization. Thus, the complexity of a graphical realization may be defined in terms of the dimensions of the local constraint codes. In this talk, we will give an overview of graphical realizations, and what is known about the complexity of graphical realizations of a linear code.

Bio: Navin Kashyap received the B.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay, in 1995, the M.S. degree in Electrical Engineering from the University of Missouri-Rolla in 1997, and the M.S. degree in Mathematics and the Ph.D. degree in Electrical Engineering from the University of Michigan, Ann Arbor, in 2001.

From November 2001 to November 2003, he was a postdoctoral research associate at the University of California, San Diego. In January 2004, he joined the Department of Mathematics and Statistics at Queen's University, Kingston, Ontario, where he is currently an Associate Professor. His research interests lie primarily in the application of combinatorial methods in information and coding theory.

Dr. Kashyap is currently visiting the ECE Department at the Indian Institute of Science, Bangalore, on sabbatical from Queen's.