Locality in Codes and Computation | Richard M. Karp Distinguished Lecture

Local algorithms are highly efficient randomized algorithms that make decisions after only reading a small portion of the input. Some of the early discoveries of such algorithms can be viewed, in retrospect, as local algorithms for error detection or correction of error-correcting codes. On the other hand, local algorithms for error-correcting codes, as well as the techniques underlying them, played a central role in the theory of computation, with applications ranging from showing hardness of fundamental computational problems to obtaining private cryptocurrency.

In this talk, Noga Ron-Zewi will describe these connections and will also highlight some of the most interesting challenges that remain in the design of local algorithms for error-correcting codes, and their use in the theory of computation.

Noga Ron-Zewi is an associate professor in the Department of Computer Science at the University of Haifa. Her research interests are at the interface of coding theory, complexity, and algorithms, and she currently heads an ERC project on “error-correcting codes and computation."

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science, and is geared toward a broad scientific audience.

Light refreshments will be available prior to the start of the lecture. 

The lecture recording URL will be emailed to registered participants. This URL can be used for immediate access to the livestream and recorded lecture. Lecture recordings will be publicly available on SimonsTV about 12 to 15 days following each presentation unless otherwise noted.

The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents [at] berkeley.edu with as much advance notice as possible.