2012/11/28 by Michelle Effros, Effros, Michelle, Salim El Rouayheb +3 · 30 citations
Computer Science · Engineering · Mathematics · #Algorithm #Coding (social sciences) #Coding tree unit #Computer network #Computer science #Context-adaptive binary arithmetic coding #Cooperative Communication and Network Coding #Discrete Mathematics (cs.DM) #Discrete mathematics #Equivalence (formal languages) #FOS: Computer and information sciences #Full-Duplex Wireless Communications #Information Theory (cs.IT) #Linear network coding #Mathematics #Networking and Internet Architecture (cs.NI) #Shannon–Fano coding #Statistics #Theoretical computer science #Tunstall coding #Variable-length code #Wireless Communication Security Techniques #cs.DM #cs.IT #cs.NI #math.IT
paper · pdf · doi:10.48550/arxiv.1211.6660
published in arXiv (Cornell University) (Cornell University)
arxiv created 2012/11/28 · openalex publication_date 2012/11/28 · arxiv updated 2012/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We show that the network coding and index coding problems are equivalent. This equivalence holds in the general setting which includes linear and non-linear codes. Specifically, we present an efficient reduction that maps a network coding instance to an index coding one while preserving feasibility. Previous connections were restricted to the linear case.