Local Testing and Decoding of Sparse Linear Codes
Presenter
February 22, 2011
Keywords:
- Computer Science and Discrete Mathematics (CSDM)
Abstract
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.)