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
chenztan@umd.edu

Communication, Control and Signal Processing Seminar

Sharp Thresholds for Random Subspaces, and Applications to LDPC Codes

Mary Wootters
Stanford University

https://umd.zoom.us/j/91596759189

Abstract
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

 

December 2020

SU MO TU WE TH FR SA
29 30 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
Submit an Event