Bounding the Optimal Rate of the ICSI and ICCSI problem

DOI10.1137/16M107164XMaRDI QIDQ5275436zbMATH OpenOpenAlexFDO

Authors Eimear Byrne, Marco Calderini

Publication date 14 July 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

broadcast with side informationcoded side informationindex codingmin-ranknetwork coding

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Communication theory (94A05)

Abstract: In this work we study both the index coding with side information (ICSI) problem introduced by Birk and Kol in 1998 and the more general problem of index coding with coded side information (ICCSI), described by Shum et al in 2012. We estimate the optimal rate of an instance of the index coding problem. In the ICSI problem case, we characterize those digraphs having min-rank one less than their order and we give an upper bound on the min-rank of a hypergraph whose incidence matrix can be associated with that of a 2-design. Security aspects are discussed in the particular case when the design is a projective plane. For the coded side information case, we extend the graph theoretic upper bounds given by Shanmugam et al in 2014 on the optimal rate of index code.

Recommendations

• The design of an optimal decision-making algorithm for fertilization
• scientific article; zbMATH DE number 26862
• Optimal control of dosage decisions in controlled ovarian hyperstimulation
• Uncertainty in clinical data and stochastic model for in vitro fertilization
• Convex Optimization of the Basic Reproduction Number
• Optimal rates and trade-offs in multiple testing
• Optimal birth control of population dynamics. II: Problems with free final time, phase constraints, and mini-max costs
• scientific article; zbMATH DE number 3871081

Cites work

• A course in combinatorics.
• An Equivalence Between Network Coding and Index Coding
• Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate
• Error Correction for Index Coding With Coded Side Information
• Error Correction for Index Coding With Side Information
• scientific article; zbMATH DE number 50655 (Why is no real title available?)
• scientific article; zbMATH DE number 53917 (Why is no real title available?)
• scientific article; zbMATH DE number 867473 (Why is no real title available?)
• Index Coding With Side Information
• Introduction to algorithms
• Nonlinear Index Coding Outperforming the Linear Optimum
• On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory
• On the Security of Index Coding With Side Information
• Optimal Index Codes With Near-Extreme Rates
• Orthogonal representations over finite fields and the chromatic number of graphs
• Über den \(p\)-Rang von Inzidenzmatrizen. (On the \(p\)-rank of incidence matrices)

Cited in

(1)

• Fundamentals of index coding

This page was built for publication: Bounding the Optimal Rate of the ICSI and ICCSI problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5275436)