Time+Place: Tuesday 29/12/2015 14:30 Room 337-8 Taub Bld.
Title: Fast Sublinear Algorithms for Error Detection and Correction
Speaker: Noga Ron-Zewi - CS-Lecture https://sites.google.com/site/nogazewi/
Affiliation: Institute for Advanced Study (IAS) at Princeton and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers
Host: Eli Ben-Sasson

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 two 
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)

Short 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.