The moderate complexity of low-density parity-check (LDPC) codes under
iterative decoding is attributed to the sparseness of their parity-check
matrices. In this talk, we consider information-theoretic bounds which are
related to the density of the parity-check matrix in terms of the
achievable gap (in rate) to capacity. This links the decoding complexity
under iterative message-passing decoding with the inherent gap of these
codes to capacity (even under ML decoding). The talk addresses both
memoryless binary-input output-symmetric channels and the setting of
parallel channels; the bounds are applied to LDPC codes with and without
puncturing.

This first part of this talk is based on a joint work with Prof.
Ruediger Urbanke (EPFL) where the paper was published in the IEEE Trans.
on Information Theory in July 2003. The second part of this talk
is based on a joint work with Mr. Gil Wiechman (Technion) and the two
joint journal papers with him are published in the February 2007 issue
of the IEEE Trans. on Information Theory.