Name
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) \ne 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 are locally testable. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-03685-9_45 | APPROX-RANDOM |
Keywords | Field | DocType |
general sufficient condition,tolerant linearity testing,product distribution,ne h,testable codes,linear code,general distribution,groups g,tolerantly testable,unbiased linear code,homomorphism h | Testability,Linearity testing,Abelian group,Discrete mathematics,Combinatorics,Product distribution,Linearity,Oracle,Linear code,Homomorphism,Mathematics | Conference |
Volume | ISSN | Citations |
5687 | 0302-9743 | 14 |
PageRank | References | Authors |
0.64 | 18 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Swastik Kopparty | 1 | 384 | 32.89 |
| Shubhangi Saraf | 2 | 263 | 24.55 |