Tolerant linearity testing and locally testable codes

Swastik Kopparty, Shubhangi Saraf

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings
Pages601-614
Number of pages14
DOIs
StatePublished - 2009
Externally publishedYes
Event12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 - Berkeley, CA, United States
Duration: Aug 21 2009Aug 23 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5687 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
Country/TerritoryUnited States
CityBerkeley, CA
Period8/21/098/23/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Tolerant linearity testing and locally testable codes'. Together they form a unique fingerprint.

Cite this