Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR19-122 | 9th September 2020 11:06

#### LDPC Codes Achieve List-Decoding Capacity

Revision #2
Authors: Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters
Accepted on: 9th September 2020 11:06
Keywords:

Abstract:

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieve list-decoding capacity. These are the first graph-based codes shown to have this property. Previously, the only codes known to achieve list-decoding capacity were completely random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. This result opens up a potential avenue towards truly linear-time list-decodable codes which achieve list-decoding capacity.

Our result on list decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decoding, list-recovery and average-radius list-decoding. Along the way, we give a characterization of sets of codewords that are likely to appear in a random linear code, which may be of independent interest.

Changes to previous version:

Minor typos were fixed.

Revision #1 to TR19-122 | 16th April 2020 21:31

#### LDPC Codes Achieve List-Decoding Capacity

Revision #1
Authors: Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters
Accepted on: 16th April 2020 21:31
Keywords:

Abstract:

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue towards truly linear-time list-decodable codes that achieve list-decoding capacity.

Our result on list decoding follows from a much more general result: any $\textit{local}$ property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decoding, list-recovery and average-radius list-decoding.

In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property $\mathcal{P}$, there is some $R^*$ so that random linear codes of rate slightly less than $R^*$ satisfy $\mathcal{P}$ with high probability, while random linear codes of rate slightly more than $R^*$ with high probability do not. We also give a characterization of the threshold rate $R^*$.

Changes to previous version:

In this updated version, the concept of a threshold for random linear codes is developed in more detail.

### Paper:

TR19-122 | 13th September 2019 23:15

#### LDPC Codes Achieve List-Decoding Capacity

TR19-122
Authors: Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters
Publication: 17th September 2019 02:58