Computer Science/Discrete Mathematics Seminar I

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.