CS Events

Computer Science Department Colloquium

High-rate Error Correcting Codes with Sublinear-time Decoding

 

Download as iCal file

Tuesday, October 17, 2017, 10:30am

 

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.

Speaker: Shubhangi Saraf

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 Advan

Location : CoRE A 301

Committee

Thu Nguyen

Event Type: Computer Science Department Colloquium

Abstract: 

Organization

Rutgers University, Department of Computer Science