Abstract:
In today’s world there
are huge amounts of data that need to get reliably stored or transmitted.
However, some amount of noise or corruption is inevitable. An error-correcting
code is a scheme for robustly representing data in the form of a codeword that
allows one to detect and correct errors in transmission. Locally-testable and
locally-decodable codes are special families of error-correcting codes that
admit highly efficient algorithms that detect and correct errors in sublinear
time with high probability, probing only a small number of entries of the
corrupted codeword. While locally-testable and locally-decodable codes have
been intensely studied in the past 2 decades, in recent years there has been
even further incentive for their study due to their relevance for transmission
and storage of massive data and the successful implementation of local codes in
cloud storage systems
In this talk, I will show an exponential improvement on the
best-known running time of error detection and correction algorithms for
locally-testable and locally-decodable codes. Specifically, I will
describe new families of locally-testable codes with constant rate that can
detect a constant fraction of errors in time (log n)^{O(log log n)} and new
families of locally-decodable codes of constant rate that can correct a
constant fraction of errors in time exp(\sqrt{log n}). Prior to that, the best
known running time for such codes was n^{epsilon} (for a constant epsilon)
using several, quite different, constructions.
(Based on joint work with Swastik Kopparty, Or Meir and Shubhangi Saraf)
Bio:
Noga Ron-Zewi is currently the IAS-DIMACS Postdoctoral Fellow at the Institute
for Advanced Study (IAS) at Princeton and the Center for Discrete Mathematics
and Theoretical Computer Science (DIMACS) at Rutgers. She received her Ph.D.
from the Department of Computer Science at the Technion in 2014, under the
supervision of Prof. Eli Ben-Sasson. Her research interests are in the theory
of computation, with a focus on research topics at the interface of
communication and computation. Noga is also a Rothschild fellow and received a
doctoral fellowship from the Israel Ministry of Science of Technology.