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", 
      "applications", 
      "diverse collection", 
      "code", 
      "connection", 
      "collection", 
      "topic", 
      "notion", 
      "number", 
      "theory", 
      "article", 
      "survey", 
      "years", 
      "problem", 
      "list-decoding 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-01-01T19:20", 
    "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_37.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.

112 TRIPLES      23 PREDICATES      49 URIs      39 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 N27003c05f0494da99cf5811ddfe5586c
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 Nca9bc1c08e404baab9e562ea52de6700
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree true
14 schema:isPartOf N241e8be4529d4389acba16035a3d8a96
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 list-decoding problem
26 new connections
27 notion
28 number
29 problem
30 recent years
31 survey
32 theory
33 topic
34 years
35 schema:name List Decoding: Algorithms and Applications
36 schema:pagination 25-41
37 schema:productId N9ac511207b3442a6b90bea2947a0d019
38 Nb3adaf65739b46f4ad66b811475ea447
39 schema:publisher Nefb0620f22434ea085d53c64d06305eb
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006968714
41 https://doi.org/10.1007/3-540-44929-9_3
42 schema:sdDatePublished 2022-01-01T19:20
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher Nb28f4833a89a4259b92096d305a23641
45 schema:url https://doi.org/10.1007/3-540-44929-9_3
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N0d31f99fb7f347f59ae9f2eb9045ef31 schema:familyName Ito
50 schema:givenName Takayasu
51 rdf:type schema:Person
52 N197ae2be7e2a441f985c71508653d2d7 rdf:first Nc57c16cd57c6466185287c785b4f289d
53 rdf:rest N44df29d3d895407f93ea1ae59bc65e01
54 N241e8be4529d4389acba16035a3d8a96 schema:isbn 978-3-540-44929-4
55 978-3-540-67823-6
56 schema:name Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics
57 rdf:type schema:Book
58 N27003c05f0494da99cf5811ddfe5586c rdf:first sg:person.014663420265.17
59 rdf:rest rdf:nil
60 N2713480893494083822d46d112e51a73 schema:familyName van Leeuwen
61 schema:givenName Jan
62 rdf:type schema:Person
63 N44df29d3d895407f93ea1ae59bc65e01 rdf:first N60f8cc17712c4f50a9387ee0b0cbe8f3
64 rdf:rest Nd487678ff0aa4ec99a446801f88d1859
65 N60f8cc17712c4f50a9387ee0b0cbe8f3 schema:familyName Mosses
66 schema:givenName Peter D.
67 rdf:type schema:Person
68 N9ac511207b3442a6b90bea2947a0d019 schema:name doi
69 schema:value 10.1007/3-540-44929-9_3
70 rdf:type schema:PropertyValue
71 Nb28f4833a89a4259b92096d305a23641 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 Nb3adaf65739b46f4ad66b811475ea447 schema:name dimensions_id
74 schema:value pub.1006968714
75 rdf:type schema:PropertyValue
76 Nc57c16cd57c6466185287c785b4f289d schema:familyName Hagiya
77 schema:givenName Masami
78 rdf:type schema:Person
79 Nc928b37269504f5092101a06802451ef rdf:first Nd03b806c184b4a83918b383693d4ab02
80 rdf:rest N197ae2be7e2a441f985c71508653d2d7
81 Nca9bc1c08e404baab9e562ea52de6700 rdf:first N2713480893494083822d46d112e51a73
82 rdf:rest Nc928b37269504f5092101a06802451ef
83 Nd03b806c184b4a83918b383693d4ab02 schema:familyName Watanabe
84 schema:givenName Osamu
85 rdf:type schema:Person
86 Nd487678ff0aa4ec99a446801f88d1859 rdf:first N0d31f99fb7f347f59ae9f2eb9045ef31
87 rdf:rest rdf:nil
88 Nefb0620f22434ea085d53c64d06305eb schema:name Springer Nature
89 rdf:type schema:Organisation
90 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
91 schema:name Mathematical Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
94 schema:name Pure Mathematics
95 rdf:type schema:DefinedTerm
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
100 schema:name Computation Theory and Mathematics
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
103 schema:name Data Format
104 rdf:type schema:DefinedTerm
105 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
106 schema:familyName Sudan
107 schema:givenName Madhu
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
109 rdf:type schema:Person
110 grid-institutes:grid.116068.8 schema:alternateName Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 545 Technology Square, 02139, Cambridge, MA
111 schema:name Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 545 Technology Square, 02139, Cambridge, MA
112 rdf:type schema:Organization
 




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


...