Technical Program

Paper Detail

Paper IDA.5.3
Paper Title Minimizing the alphabet size of erasure codes with restricted decoding sets
Authors Mira Gonen, Ariel University, Israel; Ishay Haviv, The Academic College of Tel Aviv-Yaffo, Israel; Michael Langberg, State University of New-York at Buffalo, United States; Alex Sprintson, Texas A&M University, United States
Session A.5: Combinatorial Coding Theory II
Presentation Lecture
Track Algebraic and Combinatorial Coding Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract A Maximum Distance Separable code over an alphabet $F$ is defined via an encoding function $C:F^k \rightarrow F^n$ that allows to retrieve a message $m \in F^k$ from the codeword $C(m)$ even after erasing any $n-k$ of its symbols. The minimum possible alphabet size of general (non-linear) MDS codes for given parameters $n$ and $k$ is unknown and forms one of the central open problems in coding theory. The paper initiates the study of the alphabet size of codes in a {\em generalized} setting where the coding scheme is required to handle a pre-specified subset of all possible erasure patterns, naturally represented by an $n$-vertex $k$-uniform hypergraph. We relate the minimum possible alphabet size of such codes to the strong chromatic number of the hypergraph and analyze the tightness of the obtained bounds for both the linear and non-linear settings. We further consider variations of the problem which allow a small probability of decoding error.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!