Shrinivas Kudekar

Post-doctoral Researcher


Email: shrini_[first_letter_of_lastname]
Phone: 001-505-667-0112 (CNLS Office)


I am currently a post-doctoral researcher at the Center for Non-linear Studies, Los Alamos National Laboratory, U.S.A.
I am working with Dr. Misha Chertkov and Dr. Jason Johnson. Below are my education details.

Research Interests

The broad area of my research is in information science. More specifically, I am interested in the design and analysis of graphical models appearing in computer and communication sciences. Iterative coding theory of error correcting codes based on graphs, random K-satisfiability of computer science, compressive sensing are few examples of systems based on graphs. I am also interested in further exploring the connections between Statistical physics, communication and computer sciences. Currently I am interested in designing approximation algorithms for hard estimation problems based on two popular techniques (i) message passing algorithms, (ii) convex and linear programming relaxations.

Research Work and Publications

Below is a brief description of the main research directions I have been pursuing. Not all the papers are available for download, since I am lazy to upload all of them :-).

Spatially Coupled Codes

Convolutional LDPC ensembles, introduced by Felstrom and Zigangirov, have excellent thresholds and these thresholds are rapidly increasing as a function of the average degree. Several variations on the basic theme have been proposed to date, all of which share the good performance characteristics of convolutional LDPC ensembles. We describe the fundamental mechanism which explains why "convolutional-like" or "spatially coupled" codes perform so well. In essence, the spatial coupling of the individual code structure has the effect of increasing the belief-propagation (BP) threshold of the new ensemble to its maximum possible value, namely the maximum-a-posteriori (MAP) threshold of the underlying ensemble. For this reason we call this phenomenon "threshold saturation." This gives an entirely new way of approaching capacity. We also demonstrate that the threshold saturation phenomena is quite general and is applicable to many problems in computer and communication science. A survey (in progress) of the research papers on Spatially coupled codes can be found at Spatially Coupled Codes and the principle of Threshold Saturation.

Convex Optimization in Communications

We consider various problems in communications like decoding of LDPC codes, transmitting over two-dimensional ISI channels (magnetic and optical storage) and model them as inference problems over graphs. Typically, optimal inference in these problems is NP-hard. We propose detectors and decoders based on linear programming which have good performance as well as low-complexity.

Statistical physics of graphical systems (Most of this work is in my Thesis)

Codes based on sparse parity-check matrices have been deployed successfully for efficient transmission of information over a variety of practically important channels. A thorough analysis of sparse parity-check codes on the binary erasure channel (BEC) has given sharp bounds on the performance of the optimal maximum a posteriori (MAP) decoder. This analysis is based on combinatorial methods and cannot be extended to the case of general channels. In joint work with Nicolas Macris, I prove that the replica solution of statistical physics provides a rigorous lower bound on the optimal performance to all sparse graph codes for transmission over general channels. In another part of our work we show that the lower bound is sharp, when considering transmission over the BEC. We accomplish this by extending the recently developed interpolation method of spin glass theory in statistical physics, to a class of sparse codes.

Data compression

We consider lossy compression of a binary symmetric source by means of a low-density generator-matrix code. We derive two lower bounds on the rate distortion function which are valid for any low-density generator-matrix code with a given node degree distribution L(x) on the set of generators and for any encoding algorithm. These bounds show that, due to the sparseness of the code, the performance is strictly bounded away from the Shannon rate-distortion function. In this sense, our bounds represent a natural generalization of Gallager's bound on the maximum rate at which low-density parity-check codes can be used for reliable transmission. Our bounds are similar in spirit to the technique recently developed by Dimakis, Wainwright, and Ramchandran, but they apply to individual codes



Title: Statistical Physics Methods for Sparse Graph Codes. [Download]

Application Material

Research Highlight
thanks to René Pfitzner for the source code and the picture :-)