Ontology type: schema:Chapter Open Access: True
2000
AUTHORS ABSTRACTOver 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... »
PAGES25-41
Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics
ISBN
978-3-540-67823-6
978-3-540-44929-4
http://scigraph.springernature.com/pub.10.1007/3-540-44929-9_3
DOIhttp://dx.doi.org/10.1007/3-540-44929-9_3
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1006968714
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
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