Deterministic Compression with Uncertain Priors View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2016-01-04

AUTHORS

Elad Haramaty, Madhu Sudan

ABSTRACT

Communication in “natural” settings, e.g., between humans, is distinctly different from that in classical designed settings, in that the former is invariably characterized by the sender and receiver not being in perfect agreement with each other. Solutions to classical communication problems thus have to overcome an extra layer of uncertainty introduced by this lack of prior agreement. One of the classical goals of communication is compression of information, and in this context lack of agreement implies that sender and receiver may not agree on the “prior” from which information is being generated. Most classical mechanisms for compressing turn out to be non-robust when sender and receiver do not agree on the prior. Juba et al. (Proc. ITCS 2011) showed that there do exists compression schemes with shared randomness between sender and receiver that do not share a prior that can compress information down roughly to its entropy. In this work, we explore the assumption of shared randomness between the sender and receiver and highlight why this assumption is problematic when dealing with natural communication. We initiate the study of deterministic compression schemes amid uncertain priors, and expose some of the mathematical facets of this problem. We show some non-trivial deterministic compression schemes, and some lower bounds on natural classes of compression schemes. We show that a full understanding of deterministic communication turns into challenging (open) questions in graph theory and communication complexity. More... »

PAGES

630-653

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-015-0107-6

DOI

http://dx.doi.org/10.1007/s00453-015-0107-6

DIMENSIONS

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


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/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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Technion, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Department of Computer Science, Technion, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Haramaty", 
        "givenName": "Elad", 
        "id": "sg:person.015752347745.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015752347745.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research New England, One Memorial Drive, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Microsoft Research New England, One Memorial Drive, 02139, 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": "2016-01-04", 
    "datePublishedReg": "2016-01-04", 
    "description": "Communication in \u201cnatural\u201d settings, e.g., between humans, is distinctly different from that in classical designed settings, in that the former is invariably characterized by the sender and receiver not being in perfect agreement with each other. Solutions to classical communication problems thus have to overcome an extra layer of uncertainty introduced by this lack of prior agreement. One of the classical goals of communication is compression of information, and in this context lack of agreement implies that sender and receiver may not agree on the \u201cprior\u201d from which information is being generated. Most classical mechanisms for compressing turn out to be non-robust when sender and receiver do not agree on the prior. Juba et al. (Proc. ITCS 2011) showed that there do exists compression schemes with shared randomness between sender and receiver that do not share a prior that can compress information down roughly to its entropy. In this work, we explore the assumption of shared randomness between the sender and receiver and highlight why this assumption is problematic when dealing with natural communication. We initiate the study of deterministic compression schemes amid uncertain priors, and expose some of the mathematical facets of this problem. We show some non-trivial deterministic compression schemes, and some lower bounds on natural classes of compression schemes. We show that a full understanding of deterministic communication turns into challenging (open) questions in graph theory and communication complexity.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-015-0107-6", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "76"
      }
    ], 
    "keywords": [
      "compression scheme", 
      "classical communication problems", 
      "compression of information", 
      "deterministic communication", 
      "communication complexity", 
      "natural communication", 
      "sender", 
      "graph theory", 
      "extra layer", 
      "communication problems", 
      "uncertain priors", 
      "communication", 
      "scheme", 
      "priors", 
      "lower bounds", 
      "natural class", 
      "information", 
      "prior agreement", 
      "challenging questions", 
      "receiver", 
      "compression", 
      "randomness", 
      "complexity", 
      "bounds", 
      "goal", 
      "solution", 
      "classical goals", 
      "work", 
      "uncertainty", 
      "assumption", 
      "class", 
      "entropy", 
      "setting", 
      "lack", 
      "highlights", 
      "facets", 
      "humans", 
      "layer", 
      "classical mechanism", 
      "theory", 
      "questions", 
      "mechanism", 
      "full understanding", 
      "understanding", 
      "perfect agreement", 
      "agreement", 
      "study", 
      "mathematical facets", 
      "problem", 
      "context lack", 
      "Most classical mechanisms", 
      "deterministic compression schemes", 
      "non-trivial deterministic compression schemes", 
      "Deterministic Compression"
    ], 
    "name": "Deterministic Compression with Uncertain Priors", 
    "pagination": "630-653", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013749370"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-015-0107-6"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-015-0107-6", 
      "https://app.dimensions.ai/details/publication/pub.1013749370"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:38", 
    "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/article/article_684.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-015-0107-6"
  }
]
 

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/s00453-015-0107-6'

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/s00453-015-0107-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-0107-6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-0107-6'


 

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

122 TRIPLES      21 PREDICATES      79 URIs      71 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-015-0107-6 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Na4ee20122617425e890823b717364101
4 schema:datePublished 2016-01-04
5 schema:datePublishedReg 2016-01-04
6 schema:description Communication in “natural” settings, e.g., between humans, is distinctly different from that in classical designed settings, in that the former is invariably characterized by the sender and receiver not being in perfect agreement with each other. Solutions to classical communication problems thus have to overcome an extra layer of uncertainty introduced by this lack of prior agreement. One of the classical goals of communication is compression of information, and in this context lack of agreement implies that sender and receiver may not agree on the “prior” from which information is being generated. Most classical mechanisms for compressing turn out to be non-robust when sender and receiver do not agree on the prior. Juba et al. (Proc. ITCS 2011) showed that there do exists compression schemes with shared randomness between sender and receiver that do not share a prior that can compress information down roughly to its entropy. In this work, we explore the assumption of shared randomness between the sender and receiver and highlight why this assumption is problematic when dealing with natural communication. We initiate the study of deterministic compression schemes amid uncertain priors, and expose some of the mathematical facets of this problem. We show some non-trivial deterministic compression schemes, and some lower bounds on natural classes of compression schemes. We show that a full understanding of deterministic communication turns into challenging (open) questions in graph theory and communication complexity.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N1e2e53b8496a4d62b7218ac16747201f
11 N6c79a1db317442dcb40874e97947397d
12 sg:journal.1047644
13 schema:keywords Deterministic Compression
14 Most classical mechanisms
15 agreement
16 assumption
17 bounds
18 challenging questions
19 class
20 classical communication problems
21 classical goals
22 classical mechanism
23 communication
24 communication complexity
25 communication problems
26 complexity
27 compression
28 compression of information
29 compression scheme
30 context lack
31 deterministic communication
32 deterministic compression schemes
33 entropy
34 extra layer
35 facets
36 full understanding
37 goal
38 graph theory
39 highlights
40 humans
41 information
42 lack
43 layer
44 lower bounds
45 mathematical facets
46 mechanism
47 natural class
48 natural communication
49 non-trivial deterministic compression schemes
50 perfect agreement
51 prior agreement
52 priors
53 problem
54 questions
55 randomness
56 receiver
57 scheme
58 sender
59 setting
60 solution
61 study
62 theory
63 uncertain priors
64 uncertainty
65 understanding
66 work
67 schema:name Deterministic Compression with Uncertain Priors
68 schema:pagination 630-653
69 schema:productId N830b72f7d08642e6a6bab80e54369576
70 Nac0054a40de94680900429a48da0bb4f
71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013749370
72 https://doi.org/10.1007/s00453-015-0107-6
73 schema:sdDatePublished 2022-01-01T18:38
74 schema:sdLicense https://scigraph.springernature.com/explorer/license/
75 schema:sdPublisher N9598baa6c78f41e8a8651b492ea83b4f
76 schema:url https://doi.org/10.1007/s00453-015-0107-6
77 sgo:license sg:explorer/license/
78 sgo:sdDataset articles
79 rdf:type schema:ScholarlyArticle
80 N1e2e53b8496a4d62b7218ac16747201f schema:issueNumber 3
81 rdf:type schema:PublicationIssue
82 N2550a5eefe024ced8210763f5e76dd53 rdf:first sg:person.014663420265.17
83 rdf:rest rdf:nil
84 N6c79a1db317442dcb40874e97947397d schema:volumeNumber 76
85 rdf:type schema:PublicationVolume
86 N830b72f7d08642e6a6bab80e54369576 schema:name doi
87 schema:value 10.1007/s00453-015-0107-6
88 rdf:type schema:PropertyValue
89 N9598baa6c78f41e8a8651b492ea83b4f schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 Na4ee20122617425e890823b717364101 rdf:first sg:person.015752347745.78
92 rdf:rest N2550a5eefe024ced8210763f5e76dd53
93 Nac0054a40de94680900429a48da0bb4f schema:name dimensions_id
94 schema:value pub.1013749370
95 rdf:type schema:PropertyValue
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
100 schema:name Data Format
101 rdf:type schema:DefinedTerm
102 sg:journal.1047644 schema:issn 0178-4617
103 1432-0541
104 schema:name Algorithmica
105 schema:publisher Springer Nature
106 rdf:type schema:Periodical
107 sg:person.014663420265.17 schema:affiliation grid-institutes:None
108 schema:familyName Sudan
109 schema:givenName Madhu
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
111 rdf:type schema:Person
112 sg:person.015752347745.78 schema:affiliation grid-institutes:grid.6451.6
113 schema:familyName Haramaty
114 schema:givenName Elad
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015752347745.78
116 rdf:type schema:Person
117 grid-institutes:None schema:alternateName Microsoft Research New England, One Memorial Drive, 02139, Cambridge, MA, USA
118 schema:name Microsoft Research New England, One Memorial Drive, 02139, Cambridge, MA, USA
119 rdf:type schema:Organization
120 grid-institutes:grid.6451.6 schema:alternateName Department of Computer Science, Technion, Haifa, Israel
121 schema:name Department of Computer Science, Technion, Haifa, Israel
122 rdf:type schema:Organization
 




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


...