Lower bounds on the graphical complexity of finite-length LDPC codes

This paper considers information-theoretic lower bounds on the graphical complexity of finite-length LDPC codes. It is assumed that the transmission of the codes takes place over a memoryless binary-input output-symmetric (MBIOS) channel, and the bounds are expressed as a function of the code performance and their achievable gap to capacity (either under ML decoding or any sub-optimal decoding algorithm). The lower bounds on the graphical complexity are compared to some explicit LDPC codes (or code ensembles), showing that these bounds are informative for considering the fundamental tradeoff which exists between the performance and graphical complexity of finite-length LDPC codes. This work relies on the full paper version.