Computer Science/Discrete Mathematics Seminar I

Thresholds for Random Subspaces, aka, LDPC Codes Achieve List-Decoding Capacity

What combinatorial properties are likely to be satisfied by a random subspace over a finite field? For example, is it likely that not too many points lie in any Hamming ball of fixed radius? What about any combinatorial rectangle of fixed side length?  We give a simple characterization of the threshold on the dimension below which this is very likely and above which this is very unlikely. Our motivation comes from error correcting codes, and we use this characterization to establish the list-decodability of random Low Density Parity-Check (LDPC) codes, up to list-decoding capacity.

This talk is based on the joint work with Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, and Shashwat Silas.

Date & Time

November 30, 2020 | 11:15am – 12:15pm

Location

Remote Access - see Zoom link below

Speakers

Mary Wootters

Affiliation

Stanford University