Deterministic compression with uncertain priors

DOI10.1007/S00453-015-0107-6zbMATH Open1353.68075arXiv1211.5718OpenAlexW2399515726MaRDI QIDQ5891037FDOQ5891037

Authors: Elad Haramaty, Madhu Sudan 

Publication date: 29 November 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We consider the task of compression of information when the source of the information and the destination do not agree on the prior, i.e., the distribution from which the information is being generated. This setting was considered previously by Kalai et al. (ICS 2011) who suggested that this was a natural model for human communication, and efficient schemes for compression here could give insights into the behavior of natural languages. Kalai et al. gave a compression scheme with nearly optimal performance, assuming the source and destination share some uniform randomness. In this work we explore the need for this randomness, and give some non-trivial upper bounds on the deterministic communication complexity for this problem. In the process we introduce a new family of structured graphs of constant fractional chromatic number whose (integral) chromatic number turns out to be a key component in the analysis of the communication complexity. We provide some non-trivial upper bounds on the chromatic number of these graphs to get our upper bound, while using lower bounds on variants of these graphs to prove lower bounds for some natural approaches to solve the communication complexity question. Tight analysis of communication complexity of our problems and the chromatic number of the underlying graphs remains open.

Full work available at URL: https://arxiv.org/abs/1211.5718

Recommendations

• Deterministic compression with uncertain priors
• scientific article; zbMATH DE number 6866309
• Communication with contextual uncertainty
• Communication with contextual uncertainty
• The Power of Shared Randomness in Uncertain Communication

zbMATH Keywords

graph coloringcommunication complexitysource coding

Mathematics Subject Classification ID

Source coding (94A29) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coloring of graphs and hypergraphs (05C15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• Title not available (Why is that?)
• A Mathematical Theory of Communication
• Communication Complexity
• A universal algorithm for sequential data compression
• Locality in Distributed Graph Algorithms
• The Communication Complexity of Correlation
• Information Equals Amortized Communication
• Deterministic coin tossing with applications to optimal parallel list ranking
• Title not available (Why is that?)
• A theory of goal-oriented communication

Cited In (4)

• Sending compressed messages to a learned receiver on a bidirectional line.
• Deterministic compression with uncertain priors
• Coloring chains for compression with uncertain priors
• Efficient prefix coding of uncertainty spaces

This page was built for publication: Deterministic compression with uncertain priors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891037)