List Decoding: Algorithms and Applications View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2000

AUTHORS

Madhu Sudan

ABSTRACT

Over the years coding theory and complexity theory have benefited from a number of mutually enriching connections. This article focuses on a new connection that has emerged between the two topics in the recent years. This connection is centered around the notion of “list-decoding” for error-correcting codes. In this survey we describe the list-decoding problem, the algorithms that have been developed, and a diverse collection of applications within complexity theory. More... »

PAGES

25-41

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44929-9_3

DOI

http://dx.doi.org/10.1007/3-540-44929-9_3

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing 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"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 545 Technology Square, 02139, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 545 Technology Square, 02139, Cambridge, MA"
          ], 
          "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": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "Over the years coding theory and complexity theory have benefited from a number of mutually enriching connections. This article focuses on a new connection that has emerged between the two topics in the recent years. This connection is centered around the notion of \u201clist-decoding\u201d for error-correcting codes. In this survey we describe the list-decoding problem, the algorithms that have been developed, and a diverse collection of applications within complexity theory.", 
    "editor": [
      {
        "familyName": "van Leeuwen", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "Watanabe", 
        "givenName": "Osamu", 
        "type": "Person"
      }, 
      {
        "familyName": "Hagiya", 
        "givenName": "Masami", 
        "type": "Person"
      }, 
      {
        "familyName": "Mosses", 
        "givenName": "Peter D.", 
        "type": "Person"
      }, 
      {
        "familyName": "Ito", 
        "givenName": "Takayasu", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44929-9_3", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67823-6", 
        "978-3-540-44929-4"
      ], 
      "name": "Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics", 
      "type": "Book"
    }, 
    "keywords": [
      "error-correcting codes", 
      "complexity theory", 
      "algorithm", 
      "new connections", 
      "recent years", 
      "decoding", 
      "diverse collection", 
      "applications", 
      "code", 
      "connection", 
      "collection", 
      "topic", 
      "notion", 
      "number", 
      "theory", 
      "article", 
      "survey", 
      "years", 
      "problem"
    ], 
    "name": "List Decoding: Algorithms and Applications", 
    "pagination": "25-41", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1006968714"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44929-9_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44929-9_3", 
      "https://app.dimensions.ai/details/publication/pub.1006968714"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:49", 
    "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_98.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44929-9_3"
  }
]
 

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/3-540-44929-9_3'

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/3-540-44929-9_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44929-9_3'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44929-9_3'


 

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

111 TRIPLES      23 PREDICATES      48 URIs      38 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44929-9_3 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 anzsrc-for:08
4 anzsrc-for:0802
5 anzsrc-for:0804
6 schema:author N185ce9f74a0a47d3a6d5a16349728e09
7 schema:datePublished 2000
8 schema:datePublishedReg 2000-01-01
9 schema:description Over the years coding theory and complexity theory have benefited from a number of mutually enriching connections. This article focuses on a new connection that has emerged between the two topics in the recent years. This connection is centered around the notion of “list-decoding” for error-correcting codes. In this survey we describe the list-decoding problem, the algorithms that have been developed, and a diverse collection of applications within complexity theory.
10 schema:editor N0dbfa57d14fd4a8dbbf971b11fa1f9ac
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree true
14 schema:isPartOf N895ebaee8abd418c9f5b8b9b46e57967
15 schema:keywords algorithm
16 applications
17 article
18 code
19 collection
20 complexity theory
21 connection
22 decoding
23 diverse collection
24 error-correcting codes
25 new connections
26 notion
27 number
28 problem
29 recent years
30 survey
31 theory
32 topic
33 years
34 schema:name List Decoding: Algorithms and Applications
35 schema:pagination 25-41
36 schema:productId N7422bbbbdb0e443e80f38da12ae14cc7
37 Na9fa6464122a42bf9afbc4b0a6b983d2
38 schema:publisher N583a8f1cc1674a26a7629746657b0ad9
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006968714
40 https://doi.org/10.1007/3-540-44929-9_3
41 schema:sdDatePublished 2022-05-20T07:49
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N8f6d21ad4dc6433188a6a14c2bd5318d
44 schema:url https://doi.org/10.1007/3-540-44929-9_3
45 sgo:license sg:explorer/license/
46 sgo:sdDataset chapters
47 rdf:type schema:Chapter
48 N0dbfa57d14fd4a8dbbf971b11fa1f9ac rdf:first N155f9599c27b476cb07a34212f2329be
49 rdf:rest N2705e21f438a46c69443fd06e9a4507c
50 N155f9599c27b476cb07a34212f2329be schema:familyName van Leeuwen
51 schema:givenName Jan
52 rdf:type schema:Person
53 N185ce9f74a0a47d3a6d5a16349728e09 rdf:first sg:person.014663420265.17
54 rdf:rest rdf:nil
55 N2705e21f438a46c69443fd06e9a4507c rdf:first N5698413739e044ab8f7e58e63d837d51
56 rdf:rest Ncb88f2c6c19d4a6c8886b0a1b8ff2d21
57 N44c91f6422e141dcacc553994348c9ae schema:familyName Ito
58 schema:givenName Takayasu
59 rdf:type schema:Person
60 N5698413739e044ab8f7e58e63d837d51 schema:familyName Watanabe
61 schema:givenName Osamu
62 rdf:type schema:Person
63 N583a8f1cc1674a26a7629746657b0ad9 schema:name Springer Nature
64 rdf:type schema:Organisation
65 N5998b2af9def49ce965f20ca53c10ca0 rdf:first N44c91f6422e141dcacc553994348c9ae
66 rdf:rest rdf:nil
67 N7422bbbbdb0e443e80f38da12ae14cc7 schema:name doi
68 schema:value 10.1007/3-540-44929-9_3
69 rdf:type schema:PropertyValue
70 N895ebaee8abd418c9f5b8b9b46e57967 schema:isbn 978-3-540-44929-4
71 978-3-540-67823-6
72 schema:name Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics
73 rdf:type schema:Book
74 N8a5390eda6ca436984618201369f707a rdf:first Ndf3d5012563b474d83d9760de6dd0bb4
75 rdf:rest N5998b2af9def49ce965f20ca53c10ca0
76 N8f6d21ad4dc6433188a6a14c2bd5318d schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 Na9fa6464122a42bf9afbc4b0a6b983d2 schema:name dimensions_id
79 schema:value pub.1006968714
80 rdf:type schema:PropertyValue
81 Nae0f86db2d6541a5b82053d4a02ce860 schema:familyName Hagiya
82 schema:givenName Masami
83 rdf:type schema:Person
84 Ncb88f2c6c19d4a6c8886b0a1b8ff2d21 rdf:first Nae0f86db2d6541a5b82053d4a02ce860
85 rdf:rest N8a5390eda6ca436984618201369f707a
86 Ndf3d5012563b474d83d9760de6dd0bb4 schema:familyName Mosses
87 schema:givenName Peter D.
88 rdf:type schema:Person
89 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
90 schema:name Mathematical Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
93 schema:name Pure Mathematics
94 rdf:type schema:DefinedTerm
95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
96 schema:name Information and Computing Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
99 schema:name Computation Theory and Mathematics
100 rdf:type schema:DefinedTerm
101 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
102 schema:name Data Format
103 rdf:type schema:DefinedTerm
104 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
105 schema:familyName Sudan
106 schema:givenName Madhu
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
108 rdf:type schema:Person
109 grid-institutes:grid.116068.8 schema:alternateName Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 545 Technology Square, 02139, Cambridge, MA
110 schema:name Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 545 Technology Square, 02139, Cambridge, MA
111 rdf:type schema:Organization
 




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


...