Locally-Testable and Locally-Decodable Codes (1/3)

Presenter(s)

Noga Ron-Zewi

University of Haifa

2021 Croucher Summer Course in Information Theory, The Chinese University of Hong Kong

Lecture

Date

Aug 23, 2021

Abstract

Locally-testable and locally-decodable codes are special families of error-correcting codes that admit highly efficient algorithms that detect and correct errors in transmission in sublinear time, probing only a small number of entries of the corrupted codeword. These codes have arisen from a variety of motivations within the theory of computation, and the study of these codes had a significant effect on coding theory as well. In this talk we will survey the motivations for the study of locally-testable and locally-decodable codes within the theory of computation and some of the state-of-the-art results. We will also highlight some of the most interesting challenges that remain.

Biography

Noga Ron-Zewi is a Senior Lecturer at the Department of Computer Science at the University of Haifa in Israel. Her research interests are in the theory of computation, with a focus on research topics at the interface of communication and computation. She received a Ph.D. degree in Computer Science from the Technion – Israel Institute of Technology in 2014. Prior to joining the University of Haifa, she was the IAS-DIMACS postdoctoral fellow with a joint position at the Institute for Advanced Study (IAS) at Princeton and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers, and a faculty member at Ben-Gurion University in Israel. She is a recipient of the Rothschild postdoctoral fellowship, the Alon Fellowship, and the Krill Prize.