Serving Every Symbol: All-Symbol PIR and Batch Codes

Avital Boruchovsky 1 , Anina Gruica 2 , Jonathan Niemann 2 , and Eitan Yaakobi ∗ · 2026

Read Serving Every Symbol: All-Symbol PIR and Batch Codes by Avital Boruchovsky 1 , Anina Gruica 2 , Jonathan Niemann 2 , and Eitan Yaakobi ∗ (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04041.txt.

Description

Avital Boruchovsky, Anina Gruica, Jonathan Niemann, and Eitan Yaakobi define a broad family of codes for private and batch retrieval where every stored symbol must be recoverable. Servers hold linear mixes of the information symbols. Any stored symbol should be rebuildable from a set number of disjoint server groups.

In the batch version, any multiset of stored symbols of that size must also be recoverable from disjoint groups. The four authors find the shortest possible length for some small cases and describe the shape of the best codes. They derive trade-offs among length, dimension, distance, and the recovery number. Classical families such as MDS codes and the simplex code are placed inside the new framework, and new cases of an open conjecture are settled.

Catalog record

CREATORAvital Boruchovsky 1 , Anina Gruica 2 , Jonathan Niemann 2 , and Eitan Yaakobi ∗
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-04041

Browse the full library · About the Tower of Babel