Skip to content Skip to navigation
Computer Science Department Colloquium
10/17/2017 10:30 am
CoRE A 301

High-rate Error Correcting Codes with Sublinear-time Decoding

Shubhangi Saraf, Rutgers University, Department of Computer Science

Faculty Host: Thu Nguyen

Abstract

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms: They give a method to encode k bit messages into n bit codewords such that even after a constant fraction of the bits of the codeword get corrupted, any bit of the original message can be recovered by only looking at a sublinear number of bits (or in some cases even a constant number of bits) of the corrupted codeword. The tradeoff between the rate of a code (i.e., the ratio k/n) and the locality/efficiency of its decoding algorithms has been  studied extensively in the past couple of decades with numerous applications to theoretical computer science, and more recently to practical data storage and retrieval.

In this talk I will survey some recent and not-so-recent results (both constructions and lower bounds) for locally decodable codes. In particular I will focus on some recent results that gave the first codes of high rate that are also efficiently  locally decodeable. I will also highlight some of the most interesting challenges that remain.

This is based on joint works with Swastik Kopparty, Or Meir,  Noga Ron-Zewi, Sergey Yekhanin.

Bio

Shubhangi Saraf is an Associate Professor of Mathematics and Computer Science at Rutgers University. She obtained her Ph.D. in Computer Science from the Massachusetts Institute of  Technology and then was a postdoctoral research at the Institute for Advanced Study in Princeton. Shubhangi’s research interests lie in the areas of theoretical computer science and discrete mathematics. Her research has focused on complexity theory, error correcting codes, algebraic computation and discrete geometry.