Deterministic compression with uncertain priors

DOI10.1007/S00453-015-0107-6MaRDI QIDQ5891037zbMATH OpenOpenAlexFDO

Authors Elad Haramaty, Madhu Sudan

Publication date 29 November 2016

Published in Algorithmica (Search for Journal in Brave)

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 5485523 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• A Mathematical Theory of Communication
• A theory of goal-oriented communication
• A universal algorithm for sequential data compression
• Communication Complexity
• Deterministic coin tossing with applications to optimal parallel list ranking
• Information Equals Amortized Communication
• Locality in Distributed Graph Algorithms
• The Communication Complexity of Correlation

Cited in

(6)

• Efficient prefix coding of uncertainty spaces
• Sending compressed messages to a learned receiver on a bidirectional line.
• An adaptive compression algorithm in a deterministic world
• Coloring chains for compression with uncertain priors
• Deterministic compression with uncertain priors
• Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor

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)