Correlation Decay for LDPC Codes

General description
Low Density Parity Check Codes nowadays form a basic paradigm of error correcting codes on graphs. The underlying graphical structure induces a distance between two bits in a codeword. An important question concerns the behavior of the correlation (or covariance) between pairs of bits as a function of the graph distance. An answer to this problem would have applications in a number of other situations.

Goal
One will have to learn techniques that have been successful in showing that correlations decay for various graphical structures. The case of LDPC codes offers new challenges but some progress can still be achieved.

Prerequisites
Have a taste for theoretical work.

Reference
S. Kudekar, N. Macris, Decay for Saprse Graph Error Correcting Codes, preprint submitted to SIDMA special issue 2009

Supervisor
Dr Nicolas Macris, LTHC, office inr134, tel (021) 693 8114, [email protected]