Local Decoding and Testing for Homomorphisms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Elena Grigorescu , Swastik Kopparty , Madhu Sudan

ABSTRACT

Locally decodable codes (LDCs) have played a central role in many recent results in theoretical computer science. The role of finite fields, and in particular, low-degree polynomials over finite fields, in the construction of these objects is well studied. However the role of group homomorphisms in the construction of such codes is not as widely studied. Here we initiate a systematic study of local decoding of codes based on group homomorphisms. We give an efficient list decoder for the class of homomorphisms from any abelian group G to a fixed abelian group H. The running time of this algorithm is bounded by a polynomial in log|G| and an agreement parameter, where the degree of the polynomial depends on H. Central to this algorithmic result is a combinatorial result bounding the number of homomorphisms that have large agreement with any function from G to H. Our results give a new generalization of the classical work of Goldreich and Levin, and give new abstractions of the list decoder of Sudan, Trevisan and Vadhan. As a by-product we also derive a simple(r) proof of the local testability (beyond the Blum-Luby-Rubinfeld bounds) of homomorphisms mapping \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb{Z}}_p^n$\end{document} to ℤp, first shown by M. Kiwi. More... »

PAGES

375-385

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-540-38044-3
978-3-540-38045-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11830924_35

DOI

http://dx.doi.org/10.1007/11830924_35

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Massachusetts Institute of Technology, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Grigorescu", 
        "givenName": "Elena", 
        "id": "sg:person.014612515147.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Massachusetts Institute of Technology, 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": "Massachusetts Institute of Technology, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Massachusetts Institute of Technology, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sudan", 
        "givenName": "Madhu", 
        "id": "sg:person.014663420265.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "Locally decodable codes (LDCs) have played a central role in many recent results in theoretical computer science. The role of finite fields, and in particular, low-degree polynomials over finite fields, in the construction of these objects is well studied. However the role of group homomorphisms in the construction of such codes is not as widely studied. Here we initiate a systematic study of local decoding of codes based on group homomorphisms. We give an efficient list decoder for the class of homomorphisms from any abelian group G to a fixed abelian group H. The running time of this algorithm is bounded by a polynomial in log|G| and an agreement parameter, where the degree of the polynomial depends on H. Central to this algorithmic result is a combinatorial result bounding the number of homomorphisms that have large agreement with any function from G to H. Our results give a new generalization of the classical work of Goldreich and Levin, and give new abstractions of the list decoder of Sudan, Trevisan and Vadhan. As a by-product we also derive a simple(r) proof of the local testability (beyond the Blum-Luby-Rubinfeld bounds) of homomorphisms mapping \\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}}_p^n$\\end{document} to \u2124p, first shown by M. Kiwi.", 
    "editor": [
      {
        "familyName": "D\u00edaz", 
        "givenName": "Josep", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Zwick", 
        "givenName": "Uri", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11830924_35", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-38044-3", 
        "978-3-540-38045-0"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "local decoding", 
      "list decoder", 
      "theoretical computer science", 
      "new abstraction", 
      "computer science", 
      "finite field", 
      "algorithmic results", 
      "decodable codes", 
      "low-degree polynomials", 
      "agreement parameters", 
      "such codes", 
      "decoder", 
      "decoding", 
      "code", 
      "homomorphism mapping", 
      "combinatorial results", 
      "algorithm", 
      "abstraction", 
      "objects", 
      "number of homomorphisms", 
      "Goldreich", 
      "Vadhan", 
      "group homomorphism", 
      "testability", 
      "homomorphism", 
      "class of homomorphisms", 
      "polynomials", 
      "construction", 
      "abelian group G", 
      "proof", 
      "new generalization", 
      "mapping", 
      "group G", 
      "results", 
      "work", 
      "recent results", 
      "field", 
      "generalization", 
      "Trevisan", 
      "class", 
      "classical work", 
      "science", 
      "number", 
      "local testability", 
      "time", 
      "testing", 
      "group H.", 
      "parameters", 
      "function", 
      "Levin", 
      "H.", 
      "degree", 
      "large agreement", 
      "central role", 
      "products", 
      "systematic study", 
      "role", 
      "kiwi", 
      "study", 
      "agreement", 
      "Central", 
      "Sudan", 
      "efficient list decoder", 
      "abelian group H."
    ], 
    "name": "Local Decoding and Testing for Homomorphisms", 
    "pagination": "375-385", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050261722"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11830924_35"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11830924_35", 
      "https://app.dimensions.ai/details/publication/pub.1050261722"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_271.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11830924_35"
  }
]
 

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/11830924_35'

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/11830924_35'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11830924_35'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11830924_35'


 

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

153 TRIPLES      23 PREDICATES      90 URIs      83 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11830924_35 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N968e0998913f4e93bb9e9ab26ecd51ae
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description Locally decodable codes (LDCs) have played a central role in many recent results in theoretical computer science. The role of finite fields, and in particular, low-degree polynomials over finite fields, in the construction of these objects is well studied. However the role of group homomorphisms in the construction of such codes is not as widely studied. Here we initiate a systematic study of local decoding of codes based on group homomorphisms. We give an efficient list decoder for the class of homomorphisms from any abelian group G to a fixed abelian group H. The running time of this algorithm is bounded by a polynomial in log|G| and an agreement parameter, where the degree of the polynomial depends on H. Central to this algorithmic result is a combinatorial result bounding the number of homomorphisms that have large agreement with any function from G to H. Our results give a new generalization of the classical work of Goldreich and Levin, and give new abstractions of the list decoder of Sudan, Trevisan and Vadhan. As a by-product we also derive a simple(r) proof of the local testability (beyond the Blum-Luby-Rubinfeld bounds) of homomorphisms mapping \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb{Z}}_p^n$\end{document} to ℤp, first shown by M. Kiwi.
7 schema:editor N3224c4380a6f4ff1bb1c74223a2ff791
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nc159b52dc1594d24988c81b1f8327b31
12 schema:keywords Central
13 Goldreich
14 H.
15 Levin
16 Sudan
17 Trevisan
18 Vadhan
19 abelian group G
20 abelian group H.
21 abstraction
22 agreement
23 agreement parameters
24 algorithm
25 algorithmic results
26 central role
27 class
28 class of homomorphisms
29 classical work
30 code
31 combinatorial results
32 computer science
33 construction
34 decodable codes
35 decoder
36 decoding
37 degree
38 efficient list decoder
39 field
40 finite field
41 function
42 generalization
43 group G
44 group H.
45 group homomorphism
46 homomorphism
47 homomorphism mapping
48 kiwi
49 large agreement
50 list decoder
51 local decoding
52 local testability
53 low-degree polynomials
54 mapping
55 new abstraction
56 new generalization
57 number
58 number of homomorphisms
59 objects
60 parameters
61 polynomials
62 products
63 proof
64 recent results
65 results
66 role
67 science
68 study
69 such codes
70 systematic study
71 testability
72 testing
73 theoretical computer science
74 time
75 work
76 schema:name Local Decoding and Testing for Homomorphisms
77 schema:pagination 375-385
78 schema:productId N63d5ce5765e143c59cd6c8f24734d1fc
79 N88d7a742fb644fafb8c09af06252bcd2
80 schema:publisher Ndafb5c56f0ac449fb30d6a1f463953ec
81 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050261722
82 https://doi.org/10.1007/11830924_35
83 schema:sdDatePublished 2022-01-01T19:16
84 schema:sdLicense https://scigraph.springernature.com/explorer/license/
85 schema:sdPublisher Nfaea1f44c5924bd095afbdf2a1d2cae9
86 schema:url https://doi.org/10.1007/11830924_35
87 sgo:license sg:explorer/license/
88 sgo:sdDataset chapters
89 rdf:type schema:Chapter
90 N2a0036e2f66e494aab10dc40911c97fe rdf:first sg:person.014663420265.17
91 rdf:rest rdf:nil
92 N3224c4380a6f4ff1bb1c74223a2ff791 rdf:first Nd39be58ae21b4afd9adccff3b2ce78e4
93 rdf:rest Nf57df1773812450d8775dffd0375f7e0
94 N63d5ce5765e143c59cd6c8f24734d1fc schema:name doi
95 schema:value 10.1007/11830924_35
96 rdf:type schema:PropertyValue
97 N88d7a742fb644fafb8c09af06252bcd2 schema:name dimensions_id
98 schema:value pub.1050261722
99 rdf:type schema:PropertyValue
100 N8de615a227944e2ca00cda4eb52b064e rdf:first Nf4a56505a05842b1b443ac045657786f
101 rdf:rest rdf:nil
102 N968e0998913f4e93bb9e9ab26ecd51ae rdf:first sg:person.014612515147.15
103 rdf:rest Nda33855442a54beda49fc3c60ce9507a
104 Naf00446e55ac4f949916fbbef68f8cc5 schema:familyName Rolim
105 schema:givenName José D. P.
106 rdf:type schema:Person
107 Nb8d7256b7e014f0b82ac87c263f52d4a rdf:first Naf00446e55ac4f949916fbbef68f8cc5
108 rdf:rest N8de615a227944e2ca00cda4eb52b064e
109 Nbb7c719980884924aa029daad8281c71 schema:familyName Jansen
110 schema:givenName Klaus
111 rdf:type schema:Person
112 Nc159b52dc1594d24988c81b1f8327b31 schema:isbn 978-3-540-38044-3
113 978-3-540-38045-0
114 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
115 rdf:type schema:Book
116 Nd39be58ae21b4afd9adccff3b2ce78e4 schema:familyName Díaz
117 schema:givenName Josep
118 rdf:type schema:Person
119 Nda33855442a54beda49fc3c60ce9507a rdf:first sg:person.014276170447.16
120 rdf:rest N2a0036e2f66e494aab10dc40911c97fe
121 Ndafb5c56f0ac449fb30d6a1f463953ec schema:name Springer Nature
122 rdf:type schema:Organisation
123 Nf4a56505a05842b1b443ac045657786f schema:familyName Zwick
124 schema:givenName Uri
125 rdf:type schema:Person
126 Nf57df1773812450d8775dffd0375f7e0 rdf:first Nbb7c719980884924aa029daad8281c71
127 rdf:rest Nb8d7256b7e014f0b82ac87c263f52d4a
128 Nfaea1f44c5924bd095afbdf2a1d2cae9 schema:name Springer Nature - SN SciGraph project
129 rdf:type schema:Organization
130 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
131 schema:name Mathematical Sciences
132 rdf:type schema:DefinedTerm
133 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
134 schema:name Pure Mathematics
135 rdf:type schema:DefinedTerm
136 sg:person.014276170447.16 schema:affiliation grid-institutes:grid.116068.8
137 schema:familyName Kopparty
138 schema:givenName Swastik
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16
140 rdf:type schema:Person
141 sg:person.014612515147.15 schema:affiliation grid-institutes:grid.116068.8
142 schema:familyName Grigorescu
143 schema:givenName Elena
144 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15
145 rdf:type schema:Person
146 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
147 schema:familyName Sudan
148 schema:givenName Madhu
149 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
150 rdf:type schema:Person
151 grid-institutes:grid.116068.8 schema:alternateName Massachusetts Institute of Technology, Cambridge, MA, USA
152 schema:name Massachusetts Institute of Technology, Cambridge, MA, USA
153 rdf:type schema:Organization
 




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


...