Hilal Assi – Nearly Optimal Constructions of PIR and Batch Codes.

Event Details

  • Date:

In this work we study two families of codes with availability, namely 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 r_P(n,k), r_B(n,k), for PIR, batch codes, respectively, where n is the number of information symbols. Previous results showed that in the binary case for any constant k, r_P(n,k) = \Theta(\sqrt{n}) and r_B(n,k)=O(\sqrt{n}\log(n)). In this work we study the asymptotic behavior of these codes for non-constant k and specifically for k=\Theta(n^\epsilon). We also study what the largest value of k is such the codes rate approaches 1, and show that for all \epsilon<1, r_P(n,n^\epsilon) = o(n), while for batch codes, this property holds for all \epsilon< 0.5.