Local Testing and Decoding of Sparse Linear Codes

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR II
Topic:Local Testing and Decoding of Sparse Linear Codes
Speaker:Shubhangi Saraf
Affiliation:Massachusetts Institute of Technology
Date:Tuesday, February 22
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/saraf

We study the local testabilty of sparse linear codes. This problem is intimately connected to the problem of tolerant linearity testing of Boolean functions under nonuniform distributions. We give linearity tests for several natural and interesting classes of distributions, and use this to show local testability for the corresponding codes. For the case of random sparse linear codes, we show the local testability and (list) decodability of such codes in the presence of very high noise rates too. Building on the methods used for the local algorithms, we also give sub-exponential *time* algorithms for list-decoding arbitrary unbiased (but not necessarily sparse) linear codes in the high-error regime. (Based on joint work with Swastik Kopparty.)