Efficient Communication Using Partial Information
Explore this paper's citation graph
Summary
The simulation method is used to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver.
- Type
- article
- Published
- 2010-05-12
- Cited by
- 7
- References
- 17
- OpenAlex
- https://openalex.org/W32072441
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:16990505
Keywords
Communication complexity, Computer science, Bounded function, Protocol (science), Theoretical computer science
References
- Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)
- Towards proving strong direct product theorems
- M. J. Fischer: On the Complexity of 2-Output Boolean Networks
- How to compress interactive communication
- On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements
- A parallel repetition theorem
- Realizing Boolean Functions on Disjoint sets of Variables
- Amortized Communication Complexity
- Informational complexity and the direct sum problem for simultaneous message complexity
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- Prior entanglement, message compression and privacy in quantum communication
- An information statistics approach to data stream and communication complexity
- A Parallel Repetition Theorem
- An information statistics approach to data stream and communication complexity
- A Direct Sum Theorem in Communication Complexity via Message Compression
- Theory and Applications of Trapdoor Functions (Extended Abstract)
- Communication Complexity: Basics
- A Mathematical Theory of Communication
- Electronic Colloquium on Computational Complexity, Report No. 151 (2006) The Communication Complexity of Correlation
Cited by
- Compression without a common prior: an information-theoretic justification for ambiguity in language
- A strong direct product theorem for two-way public coin communication complexity
- Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity
- How to compress interactive communication
- The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited
- New Strong Direct Product Results in Communication Complexity
- MIT Open Access Articles Compression without a common prior: An information-theoretic justification for ambiguity in language
Related papers
- Mining e-Mail Message Sequences from Log Data
- A security model for full-text file system search in multi-user environments
- Exploring the use of a generic spatial access method for caching and efficient retrieval of vario-scale data in a client-server architecture
- A NOVEL CAPABLE OUTLYING DATA CONTROL CHECKING PROCEDURE IN CLOUD STORAGE