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? What about any cube? We show that there is a sharp threshold on the dimension of the subspace at which the answers to these questions change from “extremely likely” to “extremely unlikely,” and moreover we give a simple characterization of this threshold for different properties. Our motivation comes from error correcting codes, and we use this characterization to make progress on the questions of list-decoding and list-recovery for random linear codes, and also to establish the list-decodability of random Low Density Parity-Check (LDPC) codes.
This talk is based on joint works with Venkat Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, and Shashwat Silas.
References
- LDPC Codes Achieve List Decoding Capacity [FOCS2020]
- Bounds for list-decoding and list-recovery of random linear codes [RANDOM2020]
- Sharp threshold rates for random codes [ITCS 2021]
Recorded Talk
Thanks to Mary for allowing us to record the talk!