Colloquium: Tuesday, October 26, 2021. Speaker: Jonathan Mosheiff (Carnegie Mellon University). Title: “Derandomization of elementary error correcting code ensembles”.
Zoom link: https://us02web.zoom.us/j/82797905845?pwd=VUxHdkwyRzZIOHdDWkF2OC92U0p6UT09
An error correcting code is a subset C of F_q^n. We usually want C to be 1) large, 2) well-spread and 3) efficiently decodable. Elementary random constructions, such as taking C to be a uniformly random linear subspace of the ambient vector space, achieve a very good trade-off between the first two desiderata, but are not amenable to algorithms. This motivates us to derandomize these constructions in a way that preserves spreadness, while adding some structure that can be used for algorithmic purposes. We discuss this line of research, focusing on two results.
1) In many settings, such as the ubiquitous model of list-decoding, the spreadness of a code can be formulated as a local and symmetric property. We show that such properties exhibit a certain threshold behavior with regard to random linear codes, in analogy to classic results about local properties of random graphs. This provides us with a framework by which to prove the spreadness of other code ensembles via reduction to the random linear code ensemble. We use such a reduction to prove that random LDPC codes are combinatorially list-decodable up to capacity (i.e., optimally).
2) A random linear code can be interpreted as the output of a random puncturing operation applied to the Hadamard code. The latter is a certain code of optimal distance. We prove that, much more generally, a random puncturing of any code of near-optimal distance is likely to be essentially as well-spread as a random linear code. Consequently, by a further reduction, we show that many Reed-Solomon codes are list-decodable up to capacity.
Based on joint works with Venkatesan Guruswami, Ray Li, Nati Linial, Peter Manohar, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas and Mary Wootters.
