אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.