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 redundancy of PIR codes. #R##N#The same lower bound was proved independently by Mary Wootters using a different method. The authors are currently working on a joint paper with a more comprehensive exposition of these results.
['Sankeerth Rao', 'Alexander Vardy']
Lower Bound on the Redundancy of PIR Codes