Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: High-rate Locally List, Recoverable Codes & Other Beasts
event speaker icon
Noga Ron-Zewi (Haifa University)
event date icon
Wednesday, 29.11.2017, 12:30
event location icon
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.