Batch codes based on lifted multiplicity codes
Rina Polyanskaya, Nikita Polyanskii · 2019
A binary k-batch code maps a binary string x of length n into a binary string y of length N, such that for every collection of k symbols from x, there exist k mutually disjoint recovering sets from y. We develop a new explicit coding construction of binary batch codes based on bivariate lifted multiplicity codes. For ε ∈ (0, 27, 0.47) and k = nε, our proposed k-batch codes improve the redundancy of previously known ones.