Lower Bound on the Redundancy of PIR Codes

Sankeerth Rao, Alexander Vardy

We prove that the redundancy of a $k$-server PIR code of dimension $s$ is $\Omega (\sqrt{s})$ for all $k\ge 3$. This coincides with a known upper bound of $O(\sqrt{s})$ on the redundanc…