Theory Seminar: High-rate Locally List, Recoverable Codes & Other Beasts

Noga Ron-Zewi (Haifa University)
Wednesday, 29.11.2017, 12:30
Taub 201

We give the first construction of high-rate locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block. In particular, our construction gives the first capacity-achieving locally list-decodable codes; the first capacity achieving globally list-decodable codes with nearly linear time list decoding algorithm; and a randomized construction of binary codes on the Gilbert-Varshamov bound that can be uniquely decoded in near-linear-time, with higher rate than was previously known. Our approach is combinatorial, and relies on a list recovery algorithm for high-rate tensor codes.

Joint work with Brett Hemenway and Mary Wootters.

Back to the index of events