Defines all-symbol PIR and batch codes, determines minimal lengths for small k and t, characterizes optimal codes, and proves new cases of the simplex code conjecture on functional batch recovery.
Lower Bound on the Redundancy of PIR Codes
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
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. Moreover, for $k=3$ and $k = 4$, we determine the lowest possible redundancy of $k$-server PIR codes exactly. Similar results were proved independently by Mary Wootters using a different method.
fields
cs.IT 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Serving Every Symbol: All-Symbol PIR and Batch Codes
Defines all-symbol PIR and batch codes, determines minimal lengths for small k and t, characterizes optimal codes, and proves new cases of the simplex code conjecture on functional batch recovery.