CCSP Seminar: Mary Wootters, Sharp Thresholds for Random Subspaces, and Applications fo LDPC Codes

Thursday, December 3, 2020
4:00 p.m.-5:30 p.m.
Online presentation
Zitan Chen

Communication, Control and Signal Processing Seminar

Sharp Thresholds for Random Subspaces, and Applications to LDPC Codes

Mary Wootters
Stanford University

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.

Audience: Graduate  Undergraduate  Faculty  Post-Docs 

remind we with google calendar


March 2021

28 1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31 1 2 3
Submit an Event