Lower Bound on the Redundancy of PIR Codes

We prove that the redundancy of a $k$-server PIR code of dimension $s$ is $\mathrm{\Omega }(\sqrt{s})$ for all $k\ge 3$. This coincides with a known upper bound of $O(\sqrt{s})$ on the redundancy of PIR codes. Moreover, for $k=3$ and $k = 4$,wedeterminethelowestpossibleredundancyof$k$-server PIR codes exactly. Similar results were proved independently by Mary Wootters using a different method.