Paper Info
Title
On Taking Advantage of Multiple Requests in Error Correcting Codes
Abstract
In most notions of locality in error correcting codes-notably locally recoverable codes (LRCs) and locally decodable codes (LDCs)-a decoder seeks to learn a single symbol of a message while looking at only a few symbols of the corresponding codeword. However, suppose that one wants to recover r > 1 symbols of the message. The two extremes are repeating the single-query algorithm r times (this is the intuition behind LRCs with availability, primitive multiset batch codes, and PIR codes) or simply running a global decoding algorithm to recover the whole thing. In this paper, we investigate what can happen in between these two extremes: at what value of r does repetition stop being a good idea? In order to begin to study this question we introduce robust batch codes, which seek to find r symbols of the message using m queries to the codeword, in the presence of erasures. We focus on the case where r = m, which can be seen as a generalization of the MDS property. Surprisingly, we show that for this notion of locality, repetition is optimal even up to very large values of r = Ω(k).
Year
DOI
Venue
2018
10.1109/ISIT.2018.8437593
2018 IEEE International Symposium on Information Theory (ISIT)
Keywords
DocType
Volume
error correcting codes,primitive multiset batch codes,multiple requests,locally recoverable codes,LRC,locally decodable codes,LDC,single-query algorithm,PIR codes,global decoding algorithm
Conference
abs/1802.00875
ISBN
Citations 
PageRank 
978-1-5386-4102-6
0
0.34
References 
Authors
15
2
Name
Order
Citations
PageRank
Prasanna Ramakrishnan100.34
Mary Wootters217225.99