Towards a reverse Newman's theorem in interactive information complexity
From MaRDI portal
Publication:343858
DOI10.1007/s00453-015-0112-9zbMath1353.68073WikidataQ59477355 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
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
Related Items
Compressing Interactive Communication Under Product Distributions, Unnamed Item, Lifting Theorems for Equality, On Slepian–Wolf Theorem with Interaction, The communication complexity of functions with large outputs, Communication and information complexity, Towards a reverse Newman's theorem in interactive information complexity, On Slepian-Wolf theorem with interaction, Simulation theorems via pseudo-random properties, Making Randomness Public in Unbounded-Round Information Complexity
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
