Tolerant Linearity Testing and Locally Testable Codes View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Swastik Kopparty , Shubhangi Saraf

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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{Z}_2^n$\end{document} are locally testable. More... »

PAGES

601-614

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-03684-2
978-3-642-03685-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03685-9_45

DOI

http://dx.doi.org/10.1007/978-3-642-03685-9_45

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1010903065


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Medical and Health Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1117", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Public Health and Health Services", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "CSAIL, MIT, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "CSAIL, MIT, 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kopparty", 
        "givenName": "Swastik", 
        "id": "sg:person.014276170447.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CSAIL, MIT, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "CSAIL, MIT, 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saraf", 
        "givenName": "Shubhangi", 
        "id": "sg:person.015177766032.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015177766032.20"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We study tolerant linearity testing under general distributions. Given groups G and H, a distribution \u03bc on G, and oracle access to a function f:G\u2009\u2192\u2009H, we consider the task of approximating the smallest \u03bc-distance of f to a homomorphism h:G\u2009\u2192\u2009H, where the \u03bc-distance between f and h is the probability that f(x)\u2009\u2260\u2009h(x) when x is drawn according to the distribution \u03bc. This question is intimately connected to local testability of linear codes.In this work, we give a general sufficient condition on the distribution \u03bc 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 \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathbb{Z}_2^n$\\end{document} are locally testable.", 
    "editor": [
      {
        "familyName": "Dinur", 
        "givenName": "Irit", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Naor", 
        "givenName": "Joseph", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03685-9_45", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03684-2", 
        "978-3-642-03685-9"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "testing", 
      "Sudan", 
      "access", 
      "conditions", 
      "number", 
      "bias", 
      "results", 
      "distribution", 
      "questions", 
      "general distribution", 
      "probability", 
      "group G", 
      "task", 
      "class", 
      "low bias", 
      "distance", 
      "linearity", 
      "proof", 
      "code", 
      "work", 
      "Kaufman", 
      "linearity testing", 
      "constant number", 
      "distribution \u03bc", 
      "linear codes", 
      "general sufficient condition", 
      "sufficient conditions", 
      "function f", 
      "homomorphism h", 
      "natural class", 
      "simple proof", 
      "oracle access", 
      "local testability", 
      "queries", 
      "testable codes", 
      "testability", 
      "product distribution"
    ], 
    "name": "Tolerant Linearity Testing and Locally Testable Codes", 
    "pagination": "601-614", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1010903065"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03685-9_45"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03685-9_45", 
      "https://app.dimensions.ai/details/publication/pub.1010903065"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:34", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_386.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-03685-9_45"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03685-9_45'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03685-9_45'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03685-9_45'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03685-9_45'


 

This table displays all metadata directly associated to this object as RDF triples.

119 TRIPLES      23 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03685-9_45 schema:about anzsrc-for:11
2 anzsrc-for:1117
3 schema:author N66d7dcb0e5b14d3380cc24ba233d6554
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{Z}_2^n$\end{document} are locally testable.
7 schema:editor Nafff2d009aa94aa88b7b728815211742
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N50cb4f3054ca48729dbdf38a1f518f61
12 schema:keywords Kaufman
13 Sudan
14 access
15 bias
16 class
17 code
18 conditions
19 constant number
20 distance
21 distribution
22 distribution μ
23 function f
24 general distribution
25 general sufficient condition
26 group G
27 homomorphism h
28 linear codes
29 linearity
30 linearity testing
31 local testability
32 low bias
33 natural class
34 number
35 oracle access
36 probability
37 product distribution
38 proof
39 queries
40 questions
41 results
42 simple proof
43 sufficient conditions
44 task
45 testability
46 testable codes
47 testing
48 work
49 schema:name Tolerant Linearity Testing and Locally Testable Codes
50 schema:pagination 601-614
51 schema:productId N8f9665c050364d41abaa0ed493c0d9f3
52 Ndbabbd071bee4e2bba0530341c065f65
53 schema:publisher N16ac2380edb044e4891036d48e56c29d
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010903065
55 https://doi.org/10.1007/978-3-642-03685-9_45
56 schema:sdDatePublished 2022-06-01T22:34
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N2b77cc9e38cf4bb380ff79814be5e30e
59 schema:url https://doi.org/10.1007/978-3-642-03685-9_45
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N0a48667c05764f80a082f11336baba98 schema:familyName Rolim
64 schema:givenName José
65 rdf:type schema:Person
66 N16ac2380edb044e4891036d48e56c29d schema:name Springer Nature
67 rdf:type schema:Organisation
68 N2b77cc9e38cf4bb380ff79814be5e30e schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 N50cb4f3054ca48729dbdf38a1f518f61 schema:isbn 978-3-642-03684-2
71 978-3-642-03685-9
72 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
73 rdf:type schema:Book
74 N54b341245aff4912944feedcf929715f schema:familyName Jansen
75 schema:givenName Klaus
76 rdf:type schema:Person
77 N661683835a054f619b48d40c12e24462 rdf:first N9a09ed41d5a84d30815dc2da58410f83
78 rdf:rest Ncc83108ff7784a5b90552fabe5802d62
79 N66d7dcb0e5b14d3380cc24ba233d6554 rdf:first sg:person.014276170447.16
80 rdf:rest N8e155701cacb4294a01b5ebf8d9759c1
81 N790fef70723747368baad22c84c11c60 rdf:first N54b341245aff4912944feedcf929715f
82 rdf:rest N661683835a054f619b48d40c12e24462
83 N8e155701cacb4294a01b5ebf8d9759c1 rdf:first sg:person.015177766032.20
84 rdf:rest rdf:nil
85 N8f9665c050364d41abaa0ed493c0d9f3 schema:name doi
86 schema:value 10.1007/978-3-642-03685-9_45
87 rdf:type schema:PropertyValue
88 N9a09ed41d5a84d30815dc2da58410f83 schema:familyName Naor
89 schema:givenName Joseph
90 rdf:type schema:Person
91 Naf6c6ca1343e44a1b093281de8d846b3 schema:familyName Dinur
92 schema:givenName Irit
93 rdf:type schema:Person
94 Nafff2d009aa94aa88b7b728815211742 rdf:first Naf6c6ca1343e44a1b093281de8d846b3
95 rdf:rest N790fef70723747368baad22c84c11c60
96 Ncc83108ff7784a5b90552fabe5802d62 rdf:first N0a48667c05764f80a082f11336baba98
97 rdf:rest rdf:nil
98 Ndbabbd071bee4e2bba0530341c065f65 schema:name dimensions_id
99 schema:value pub.1010903065
100 rdf:type schema:PropertyValue
101 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
102 schema:name Medical and Health Sciences
103 rdf:type schema:DefinedTerm
104 anzsrc-for:1117 schema:inDefinedTermSet anzsrc-for:
105 schema:name Public Health and Health Services
106 rdf:type schema:DefinedTerm
107 sg:person.014276170447.16 schema:affiliation grid-institutes:grid.116068.8
108 schema:familyName Kopparty
109 schema:givenName Swastik
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16
111 rdf:type schema:Person
112 sg:person.015177766032.20 schema:affiliation grid-institutes:grid.116068.8
113 schema:familyName Saraf
114 schema:givenName Shubhangi
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015177766032.20
116 rdf:type schema:Person
117 grid-institutes:grid.116068.8 schema:alternateName CSAIL, MIT, 02139, Cambridge, MA, USA
118 schema:name CSAIL, MIT, 02139, Cambridge, MA, USA
119 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...