An error correcting code should ideally be 1) of large rate, 2) noise tolerant and 3) efficiently decodable. Elementary probabilistic constructions, such as random linear codes, achieve an excellent trade-off between the first two objectives, but unfortunately, decoding them is believed to be algorithmically hard. This motivates us to derandomize these constructions in a way that preserves noise tolerance, while adding structure that can be used for algorithmic purposes.
In many settings, such as the ubiquitous list-decoding model, noise-tolerance can be seen to be a "local property of codes" - a new concept analogous to the classical notion of a local property of graphs. This observation turns out to yield a highly effective framework for the analysis and derandomization of elementary random codes. In this talk I will discuss the line of research that originates in the analogy between codes and graphs, and culminates, so far, in the recent proof that many Reed-Solomon codes achieve list-decoding capacity.
Based on joint works with Venkatesan Guruswami, Ray Li, Nati Linial, Peter Manohar, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas and Mary Wootters.
Jonathan Mosheiff is a postdoctoral researcher in the Computer Science Department at Carnegie Mellon University. He received a Ph.D (2018), M.Sc (2013) and B.Sc (2006) from the Hebrew University of Jerusalem. During his Ph.D, he was supported by the Adams Fellowship of the Israel Academy of Sciences and Humanities. Jonathan works in theoretical computer science, information theory and combinatorics, and is particularly interested in coding theory and property testing.