Towards a reverse Newman's theorem in interactive information complexity

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

zbMATH Keywords

compressioninformation theoryinformation complexitycommunication complexitySlepian-Wolf

Mathematics Subject Classification ID

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 (10)

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

This page was built for publication: Towards a reverse Newman's theorem in interactive information complexity