"Thresholds for local properties of random and LDPC codes"
Jonathan Mosheiff (CMU)
Monday October 12 2-3pm
Abstract: A (q-ary) random linear code of rate R is a uniformly sampled Rn-dimensional subspace of the n dimensional vector space over the field F_q. Such codes are among the most basic and important constructions in coding theory.
We define the notion of a local and symmetric property, namely, this is a property characterized by the code not containing certain kinds of small forbidden sets of codewords. In particular, the widely studied concepts of list-decodability and list-recoverability can be naturally formulated as such properties. We show that local and symmetric properties have sharp thresholds for random linear codes, that is, a random linear code above a certain threshold rate R* is very likely to satisfy the property, while a random linear code below this rate is very likely not to satisfy it. We explicitly describe the threshold rate R* for a given property, and draw conclusions about list-decodability and list-recoverability of random linear codes, as well as plain random codes.
We then turn to study Gallager's classic ensemble of Low-Density Parity Check (LDPC) codes. We show that Gallager’s 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 plain random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. This result opens up a potential avenue towards the construction of linear-time list-decodable codes which achieve list-decoding capacity.
Based on joint works with Venkat Guruswami, Ray Li, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas and Mary Wootters.