Towards a reverse Newman's theorem in interactive information complexity
From MaRDI portal
Publication:343858
DOI10.1007/s00453-015-0112-9zbMath1353.68073OpenAlexW3001333482WikidataQ59477355 ScholiaQ59477355MaRDI QIDQ343858
Florian Speelman, Joshua Brody, Michal Koucký, Bruno Loff, Harry Buhrman, Nikolai K. Vereshchagin
Publication date: 29 November 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-0112-9
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Related Items
On Slepian-Wolf theorem with interaction, Towards a reverse Newman's theorem in interactive information complexity, Making Randomness Public in Unbounded-Round Information Complexity, The communication complexity of functions with large outputs, Communication and information complexity, Compressing Interactive Communication Under Product Distributions, On Slepian–Wolf Theorem with Interaction, Unnamed Item, Simulation theorems via pseudo-random properties, Lifting Theorems for Equality
Cites Work
- Unnamed Item
- A direct product theorem for two-party bounded-round public-coin communication complexity
- Towards a reverse Newman's theorem in interactive information complexity
- An information statistics approach to data stream and communication complexity
- Private vs. common random bits in communication complexity
- How to compress interactive communication
- Computing with Noisy Information
- On Representatives of Subsets
- Public vs Private Coin in Bounded-Round Information
- Direct Product via Round-Preserving Compression
- Internal Compression of Protocols to Entropy
- Simple and Tight Bounds for Information Reconciliation and Privacy Amplification
- Information Equals Amortized Communication
- Noiseless coding of correlated information sources
