Title: Nearly Optimal Constructions of PIR and Batch Codes,
Abstract: 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 $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 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 the largest value of $k$ such that the
rate of the codes 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$.