2017/01/25 by Asi, Hilal, Yaakobi, Eitan
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1701.07206
In this work we study two families of codes with availability, namely private information retrieval (PIR) codes and batch codes. While the former requires that every information symbol has k mutually disjoint recovering sets, the latter asks this property for every multiset request of k information symbols. The main problem under this paradigm is to minimize the number of redundancy symbols. We denote this value by rP(n,k), rB(n,k), for PIR, batch codes, respectively, where n is the number of information symbols. Previous results showed that for any constant k, rP(n,k) = Θ(√(n)) and rB(n,k)=O(√(n)log(n). In this work we study the asymptotic behavior of these codes for non-constant k and specifically for k=Θ(nε). We also study the largest value of k such that the rate of the codes approaches 1, and show that for all ε<1, rP(n,nε) = o(n), while for batch codes, this property holds for all ε< 0.5.