School of Mathematics

Local Testing and Decoding of Sparse Linear Codes

Shubhangi Saraf
Massachusetts Institute of Technology
February 22, 2011

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.