Technical Program

Paper Detail

Paper IDM.4.4
Paper Title A Combinatorial View of the Service Rates of Codes Problem, its Equivalence to Fractional Matching and its Connection with Batch Codes
Authors Fatemeh Kazemi, Esmaeil Karimi, Texas A&M University, United States; Emina Soljanin, Rutgers University, United States; Alex Sprintson, Texas A&M University, United States
Session M.4: Codes for Distributed Storage IV
Presentation Lecture
Track Coding for Storage and Memories
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract We propose a novel technique for constructing a graph representation of a code through which we establish a significant connection between the service rate problem and the well-known fractional matching problem. Using this connection, we show that the service capacity of a coded storage system equals the fractional matching number in the graph representation of the code, and thus is lower bounded and upper bounded by the matching number and the vertex cover number, respectively. This is of great interest because if the graph representation of a code is bipartite, then the derived upper and lower bounds are equal, and we obtain the capacity. Leveraging this result, we characterize the service capacity of the binary simplex code whose graph representation is bipartite. Moreover, we show that the service rate problem can be viewed as a generalization of the multiset primitive batch codes problem.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!