The Taub Faculty of Computer Science Events and Talks

In this work we study two families of codes with availability, namely \emph{PIR codes} and \emph{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)=\cO(\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$.