TY - GEN

T1 - Tolerant linearity testing and locally testable codes

AU - Kopparty, Swastik

AU - Saraf, Shubhangi

PY - 2009

Y1 - 2009

N2 - We study tolerant linearity testing under general distributions. Given groups G and H, a distribution μ on G, and oracle access to a function f:G → H, we consider the task of approximating the smallest μ-distance of f to a homomorphism h : G → H, where the μ-distance between f and h is the probability that f(x) ≠ h(x) when x is drawn according to the distribution μ. This question is intimately connected to local testability of linear codes. In this work, we give a general sufficient condition on the distribution μ for linearity to be tolerantly testable with a constant number of queries. Using this condition we show that linearity is tolerantly testable for several natural classes of distributions including low bias, symmetric and product distributions. This gives a new and simple proof of a result of Kaufman and Sudan which shows that sparse, unbiased linear codes over ℤ 2n are locally testable.

AB - We study tolerant linearity testing under general distributions. Given groups G and H, a distribution μ on G, and oracle access to a function f:G → H, we consider the task of approximating the smallest μ-distance of f to a homomorphism h : G → H, where the μ-distance between f and h is the probability that f(x) ≠ h(x) when x is drawn according to the distribution μ. This question is intimately connected to local testability of linear codes. In this work, we give a general sufficient condition on the distribution μ for linearity to be tolerantly testable with a constant number of queries. Using this condition we show that linearity is tolerantly testable for several natural classes of distributions including low bias, symmetric and product distributions. This gives a new and simple proof of a result of Kaufman and Sudan which shows that sparse, unbiased linear codes over ℤ 2n are locally testable.

UR - http://www.scopus.com/inward/record.url?scp=70350587315&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350587315&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03685-9_45

DO - 10.1007/978-3-642-03685-9_45

M3 - Conference contribution

AN - SCOPUS:70350587315

SN - 3642036848

SN - 9783642036842

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 601

EP - 614

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009

Y2 - 21 August 2009 through 23 August 2009

ER -