Binary Batch Codes with Improved Redundancy

Rina Polyanskaya, Nikita Polyanskii, Ilya Vorobyev

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


A primitive $k$ -batch code encodes a string $\boldsymbol {x}$ of length $n$ into a string $\boldsymbol {y}$ of length $N$ , such that each multiset of $k$ symbols from $\boldsymbol {x}$ has $k$ mutually disjoint recovering sets from $\boldsymbol {y}$. In this paper, we discuss new constructions of binary primitive batch codes. First, we develop novel explicit and random coding constructions of linear primitive batch codes based on finite geometries. Second, a new explicit coding construction of binary primitive batch codes based on bivariate lifted multiplicity codes is provided. For any $k=n^ \varepsilon $ with $\varepsilon \in (0,0.47)\setminus \{1/5,1/4\}$ , our proposed codes have a better trade-off between the redundancy and the parameters $k,n$ than previously known batch codes.

Original languageEnglish
Article number9154365
Pages (from-to)7360-7370
Number of pages11
JournalIEEE Transactions on Information Theory
Issue number12
Publication statusPublished - Dec 2020


  • Disjoint recovering sets
  • finite geometry
  • lifted multiplicity codes
  • primitive batch codes


Dive into the research topics of 'Binary Batch Codes with Improved Redundancy'. Together they form a unique fingerprint.

Cite this