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": [
      "finite field", 
      "group homomorphism", 
      "theoretical computer science", 
      "class of homomorphisms", 
      "low-degree polynomials", 
      "abelian group G", 
      "number of homomorphisms", 
      "local decoding", 
      "combinatorial results", 
      "new generalization", 
      "group G", 
      "algorithmic results", 
      "homomorphism", 
      "homomorphism mapping", 
      "polynomials", 
      "recent results", 
      "such codes", 
      "classical work", 
      "decodable codes", 
      "computer science", 
      "field", 
      "generalization", 
      "systematic study", 
      "list decoder", 
      "local testability", 
      "group H.", 
      "code", 
      "Goldreich", 
      "algorithm", 
      "proof", 
      "Trevisan", 
      "class", 
      "Vadhan", 
      "construction", 
      "parameters", 
      "Levin", 
      "decoding", 
      "agreement parameters", 
      "decoder", 
      "results", 
      "H.", 
      "objects", 
      "agreement", 
      "new abstraction", 
      "function", 
      "number", 
      "mapping", 
      "work", 
      "science", 
      "large agreement", 
      "time", 
      "degree", 
      "abstraction", 
      "central role", 
      "testability", 
      "products", 
      "role", 
      "study", 
      "testing", 
      "kiwi", 
      "Central", 
      "Sudan"
    ], 
    "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-05-20T07:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_179.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.

151 TRIPLES      23 PREDICATES      88 URIs      81 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 N9ff84c83224b442cb6d07bf50a8e49cc
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 N6573beefc52340419e94acc592630a91
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3636d56543064932a1b618a9e1a5c31e
12 schema:keywords Central
13 Goldreich
14 H.
15 Levin
16 Sudan
17 Trevisan
18 Vadhan
19 abelian group G
20 abstraction
21 agreement
22 agreement parameters
23 algorithm
24 algorithmic results
25 central role
26 class
27 class of homomorphisms
28 classical work
29 code
30 combinatorial results
31 computer science
32 construction
33 decodable codes
34 decoder
35 decoding
36 degree
37 field
38 finite field
39 function
40 generalization
41 group G
42 group H.
43 group homomorphism
44 homomorphism
45 homomorphism mapping
46 kiwi
47 large agreement
48 list decoder
49 local decoding
50 local testability
51 low-degree polynomials
52 mapping
53 new abstraction
54 new generalization
55 number
56 number of homomorphisms
57 objects
58 parameters
59 polynomials
60 products
61 proof
62 recent results
63 results
64 role
65 science
66 study
67 such codes
68 systematic study
69 testability
70 testing
71 theoretical computer science
72 time
73 work
74 schema:name Local Decoding and Testing for Homomorphisms
75 schema:pagination 375-385
76 schema:productId N72ccdb7c319541048a2d56ce73561ac2
77 Nce9853f5a83a4b27a310d4f56bab695f
78 schema:publisher Nbf3a170a784748c580ada769c21b2408
79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050261722
80 https://doi.org/10.1007/11830924_35
81 schema:sdDatePublished 2022-05-20T07:42
82 schema:sdLicense https://scigraph.springernature.com/explorer/license/
83 schema:sdPublisher N69b82f07d45c4e7c9acfea305fa88e9b
84 schema:url https://doi.org/10.1007/11830924_35
85 sgo:license sg:explorer/license/
86 sgo:sdDataset chapters
87 rdf:type schema:Chapter
88 N35e065f882504b4ab6a862831fdaf5be rdf:first N96583f22a69c4210ad5e19dd9245837f
89 rdf:rest rdf:nil
90 N3636d56543064932a1b618a9e1a5c31e schema:isbn 978-3-540-38044-3
91 978-3-540-38045-0
92 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
93 rdf:type schema:Book
94 N41ac8458bdd84f8f962c709c7ca478e9 rdf:first N474f0882ecf94ba5bf930a5de343761d
95 rdf:rest Ne11246c126f649df8d61469c3649aca6
96 N474f0882ecf94ba5bf930a5de343761d schema:familyName Jansen
97 schema:givenName Klaus
98 rdf:type schema:Person
99 N6573beefc52340419e94acc592630a91 rdf:first N7624f1fd78754101bb0146a550756821
100 rdf:rest N41ac8458bdd84f8f962c709c7ca478e9
101 N69b82f07d45c4e7c9acfea305fa88e9b schema:name Springer Nature - SN SciGraph project
102 rdf:type schema:Organization
103 N72ccdb7c319541048a2d56ce73561ac2 schema:name dimensions_id
104 schema:value pub.1050261722
105 rdf:type schema:PropertyValue
106 N7624f1fd78754101bb0146a550756821 schema:familyName Díaz
107 schema:givenName Josep
108 rdf:type schema:Person
109 N96583f22a69c4210ad5e19dd9245837f schema:familyName Zwick
110 schema:givenName Uri
111 rdf:type schema:Person
112 N9ff84c83224b442cb6d07bf50a8e49cc rdf:first sg:person.014612515147.15
113 rdf:rest Nb647db00bf654dd99413649414941ca9
114 Nb647db00bf654dd99413649414941ca9 rdf:first sg:person.014276170447.16
115 rdf:rest Nfbdc7541ac3f4d2b94aa51e344cc60a9
116 Nbf3a170a784748c580ada769c21b2408 schema:name Springer Nature
117 rdf:type schema:Organisation
118 Nce9853f5a83a4b27a310d4f56bab695f schema:name doi
119 schema:value 10.1007/11830924_35
120 rdf:type schema:PropertyValue
121 Ne11246c126f649df8d61469c3649aca6 rdf:first Ned4d3008fa4641639dc15cd3f0293784
122 rdf:rest N35e065f882504b4ab6a862831fdaf5be
123 Ned4d3008fa4641639dc15cd3f0293784 schema:familyName Rolim
124 schema:givenName José D. P.
125 rdf:type schema:Person
126 Nfbdc7541ac3f4d2b94aa51e344cc60a9 rdf:first sg:person.014663420265.17
127 rdf:rest rdf:nil
128 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
129 schema:name Mathematical Sciences
130 rdf:type schema:DefinedTerm
131 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
132 schema:name Pure Mathematics
133 rdf:type schema:DefinedTerm
134 sg:person.014276170447.16 schema:affiliation grid-institutes:grid.116068.8
135 schema:familyName Kopparty
136 schema:givenName Swastik
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16
138 rdf:type schema:Person
139 sg:person.014612515147.15 schema:affiliation grid-institutes:grid.116068.8
140 schema:familyName Grigorescu
141 schema:givenName Elena
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15
143 rdf:type schema:Person
144 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
145 schema:familyName Sudan
146 schema:givenName Madhu
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
148 rdf:type schema:Person
149 grid-institutes:grid.116068.8 schema:alternateName Massachusetts Institute of Technology, Cambridge, MA, USA
150 schema:name Massachusetts Institute of Technology, Cambridge, MA, USA
151 rdf:type schema:Organization
 




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


...