Modelling Errors and Recovery for Communication View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Madhu Sudan

ABSTRACT

The theory of error-correction has had two divergent schools of thought, going back to the works of Shannon and Hamming. In the Shannon school, error is presumed to have been effected probabilistically. In the Hamming school, the error is modeled as effected by an all-powerful adversary. The two schools lead to drastically different limits. In the Shannon model, a binary channel with error-rate close to, but less than, 50% is useable for effective communication. In the Hamming model, a binary channel with an error-rate of more than 25% prohibits unique recovery of the message.In this talk, we describe the notion of list-decoding, as a bridge between the Hamming and Shannon models. This model relaxes the notion of recovery to allow for a “list of candidates”. We describe results in this model, and then show how these results can be applied to get unique recovery under “computational restrictions” on the channel’s ability, a model initiated by R. Lipton in 1994.Based on joint works with Venkatesan Guruswami (U. Washington), and with Silvio Micali (MIT), Chris Peikert (MIT) and David Wilson (MIT). More... »

PAGES

25-25

Book

TITLE

LATIN 2006: Theoretical Informatics

ISBN

978-3-540-32755-4
978-3-540-32756-1

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11682462_5

DOI

http://dx.doi.org/10.1007/11682462_5

DIMENSIONS

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


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/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "MIT, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT, Cambridge, 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": "The theory of error-correction has had two divergent schools of thought, going back to the works of Shannon and Hamming. In the Shannon school, error is presumed to have been effected probabilistically. In the Hamming school, the error is modeled as effected by an all-powerful adversary. The two schools lead to drastically different limits. In the Shannon model, a binary channel with error-rate close to, but less than, 50% is useable for effective communication. In the Hamming model, a binary channel with an error-rate of more than 25% prohibits unique recovery of the message.In this talk, we describe the notion of list-decoding, as a bridge between the Hamming and Shannon models. This model relaxes the notion of recovery to allow for a \u201clist of candidates\u201d. We describe results in this model, and then show how these results can be applied to get unique recovery under \u201ccomputational restrictions\u201d on the channel\u2019s ability, a model initiated by R.\u00a0Lipton in 1994.Based on joint works with Venkatesan Guruswami (U. Washington), and with Silvio Micali (MIT), Chris Peikert (MIT) and David Wilson (MIT).", 
    "editor": [
      {
        "familyName": "Correa", 
        "givenName": "Jos\u00e9 R.", 
        "type": "Person"
      }, 
      {
        "familyName": "Hevia", 
        "givenName": "Alejandro", 
        "type": "Person"
      }, 
      {
        "familyName": "Kiwi", 
        "givenName": "Marcos", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11682462_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-32755-4", 
        "978-3-540-32756-1"
      ], 
      "name": "LATIN 2006: Theoretical Informatics", 
      "type": "Book"
    }, 
    "keywords": [
      "work of Shannon", 
      "notion of recovery", 
      "effective communication", 
      "schools", 
      "divergent schools", 
      "ability", 
      "thought", 
      "communication", 
      "notion", 
      "talk", 
      "theory", 
      "error", 
      "model", 
      "messages", 
      "list", 
      "work", 
      "results", 
      "computational restrictions", 
      "unique recovery", 
      "joint work", 
      "recovery", 
      "different limits", 
      "Shannon model", 
      "Wilson", 
      "powerful adversary", 
      "binary channel", 
      "list of candidates", 
      "Hamming", 
      "restriction", 
      "modelling error", 
      "Shannon", 
      "adversary", 
      "Micali", 
      "Peikert", 
      "Guruswami", 
      "candidates", 
      "bridge", 
      "channels", 
      "channel's ability", 
      "Lipton", 
      "limit", 
      "Shannon school", 
      "Hamming school", 
      "Hamming model", 
      "Venkatesan Guruswami", 
      "Silvio Micali", 
      "Chris Peikert", 
      "David Wilson"
    ], 
    "name": "Modelling Errors and Recovery for Communication", 
    "pagination": "25-25", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018607239"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11682462_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11682462_5", 
      "https://app.dimensions.ai/details/publication/pub.1018607239"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:26", 
    "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_50.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11682462_5"
  }
]
 

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/11682462_5'

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/11682462_5'

Turtle is a human-readable linked data format.

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

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

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


 

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

118 TRIPLES      23 PREDICATES      74 URIs      67 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11682462_5 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author Neb2a4d7cca73410a864e80ec081e46d0
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description The theory of error-correction has had two divergent schools of thought, going back to the works of Shannon and Hamming. In the Shannon school, error is presumed to have been effected probabilistically. In the Hamming school, the error is modeled as effected by an all-powerful adversary. The two schools lead to drastically different limits. In the Shannon model, a binary channel with error-rate close to, but less than, 50% is useable for effective communication. In the Hamming model, a binary channel with an error-rate of more than 25% prohibits unique recovery of the message.In this talk, we describe the notion of list-decoding, as a bridge between the Hamming and Shannon models. This model relaxes the notion of recovery to allow for a “list of candidates”. We describe results in this model, and then show how these results can be applied to get unique recovery under “computational restrictions” on the channel’s ability, a model initiated by R. Lipton in 1994.Based on joint works with Venkatesan Guruswami (U. Washington), and with Silvio Micali (MIT), Chris Peikert (MIT) and David Wilson (MIT).
7 schema:editor Nc3a5577fba7b494ba1475b9ae607563e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N334b8212b6e141fbab391894398c8e2b
12 schema:keywords Chris Peikert
13 David Wilson
14 Guruswami
15 Hamming
16 Hamming model
17 Hamming school
18 Lipton
19 Micali
20 Peikert
21 Shannon
22 Shannon model
23 Shannon school
24 Silvio Micali
25 Venkatesan Guruswami
26 Wilson
27 ability
28 adversary
29 binary channel
30 bridge
31 candidates
32 channel's ability
33 channels
34 communication
35 computational restrictions
36 different limits
37 divergent schools
38 effective communication
39 error
40 joint work
41 limit
42 list
43 list of candidates
44 messages
45 model
46 modelling error
47 notion
48 notion of recovery
49 powerful adversary
50 recovery
51 restriction
52 results
53 schools
54 talk
55 theory
56 thought
57 unique recovery
58 work
59 work of Shannon
60 schema:name Modelling Errors and Recovery for Communication
61 schema:pagination 25-25
62 schema:productId N11a617b35f2b4113af37ab0992b0347c
63 N6d0c831fe9a549479c05bcdf7547369f
64 schema:publisher N6d895d022dd74b04b297bacbf2a8770a
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018607239
66 https://doi.org/10.1007/11682462_5
67 schema:sdDatePublished 2022-01-01T19:26
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher Nfe0b4597fe6a47269ceaf114abb91597
70 schema:url https://doi.org/10.1007/11682462_5
71 sgo:license sg:explorer/license/
72 sgo:sdDataset chapters
73 rdf:type schema:Chapter
74 N11a617b35f2b4113af37ab0992b0347c schema:name dimensions_id
75 schema:value pub.1018607239
76 rdf:type schema:PropertyValue
77 N2a798d28a6d346109bfb5438b2a96d2b schema:familyName Hevia
78 schema:givenName Alejandro
79 rdf:type schema:Person
80 N334b8212b6e141fbab391894398c8e2b schema:isbn 978-3-540-32755-4
81 978-3-540-32756-1
82 schema:name LATIN 2006: Theoretical Informatics
83 rdf:type schema:Book
84 N3709e13e8001495084584a41aebbd94e rdf:first N2a798d28a6d346109bfb5438b2a96d2b
85 rdf:rest Na4a372b89dc74d44a7cfda82bd410d78
86 N6d0c831fe9a549479c05bcdf7547369f schema:name doi
87 schema:value 10.1007/11682462_5
88 rdf:type schema:PropertyValue
89 N6d895d022dd74b04b297bacbf2a8770a schema:name Springer Nature
90 rdf:type schema:Organisation
91 Na4a372b89dc74d44a7cfda82bd410d78 rdf:first Nfb07a1734011453485a4f84222bd1cb2
92 rdf:rest rdf:nil
93 Na7a164583d544a74b6f8031b899aade0 schema:familyName Correa
94 schema:givenName José R.
95 rdf:type schema:Person
96 Nc3a5577fba7b494ba1475b9ae607563e rdf:first Na7a164583d544a74b6f8031b899aade0
97 rdf:rest N3709e13e8001495084584a41aebbd94e
98 Neb2a4d7cca73410a864e80ec081e46d0 rdf:first sg:person.014663420265.17
99 rdf:rest rdf:nil
100 Nfb07a1734011453485a4f84222bd1cb2 schema:familyName Kiwi
101 schema:givenName Marcos
102 rdf:type schema:Person
103 Nfe0b4597fe6a47269ceaf114abb91597 schema:name Springer Nature - SN SciGraph project
104 rdf:type schema:Organization
105 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
106 schema:name Psychology and Cognitive Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
109 schema:name Psychology
110 rdf:type schema:DefinedTerm
111 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
112 schema:familyName Sudan
113 schema:givenName Madhu
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
115 rdf:type schema:Person
116 grid-institutes:grid.116068.8 schema:alternateName MIT, Cambridge, USA
117 schema:name MIT, Cambridge, USA
118 rdf:type schema:Organization
 




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


...