Computer Science/Discrete Mathematics Seminar II

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