Computer Science Department Colloquium
High-rate Error Correcting Codes with Sublinear-time Decoding
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
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
Event Type: Computer Science Department Colloquium
Rutgers University, Department of Computer Science