Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem

DOI10.1007/978-3-662-48054-0_20zbMath1466.68038arXiv1511.02899OpenAlexW2149723766MaRDI QIDQ2946394

Daniyar Chumbalov, Andrei Romashchenko

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

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

zbMATH Keywords

coding theorycommunication complexitySlepian-Wolf codingpseudo-random permutationsrandomized encoding

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Randomized algorithms (68W20) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial version of the Slepian-Wolf coding theorem for binary strings
• Inequalities for Shannon entropy and Kolmogorov complexity
• Interactive Communication of Balanced Distributions and of Correlated Files
• Noiseless coding of correlated information sources
• Information Theory
• Conditional complexity and codes
• Combinatorial interpretation of Kolmogorov complexity