Nearly Optimal Constructions of PIR and Batch Codes

DOI10.1109/TIT.2018.2852294MaRDI QIDQ4615354zbMATH OpenOpenAlexWikidataFDO

Authors Hilal Asi, Eitan Yaakobi

Publication date 28 January 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.07206

zbMATH Keywords

asymptotic behaviorbatch codescodes with availabilityprivate information retrieval (PIR) codes

Mathematics Subject Classification ID

Other types of codes (94B60)

Abstract: In this work we study two families of codes with availability, namely private information retrieval (PIR) codes and batch codes. While the former requires that every information symbol has $k$ mutually disjoint recovering sets, the latter asks this property for every multiset request of $k$ information symbols. The main problem under this paradigm is to minimize the number of redundancy symbols. We denote this value by $r_P(n,k),r_B(n,k)$, for PIR, batch codes, respectively, where $n$ is the number of information symbols. Previous results showed that for any constant $k$, $r_P(n,k)=Theta(sqrtn)$ and $r_B(n,k)=O(sqrtnlog(n)$. In this work we study the asymptotic behavior of these codes for non-constant $k$ and specifically for $k=Theta(n^{e}psilon)$. We also study the largest value of $k$ such that the rate of the codes approaches 1, and show that for all $epsilon<1$, $r_P(n,n^{e}psilon)=o(n)$, while for batch codes, this property holds for all $epsilon<0.5$.

Cited in

(7)

• Constructions and bounds for batch codes with small parameters
• Batch codes from affine Cartesian codes and quotient spaces
• A general private information retrieval scheme for MDS coded databases with colluding servers
• PIR codes with short block length
• Locality via partially lifted codes
• PIR Array Codes With Optimal Virtual Server Rate
• Lifted Multiplicity Codes and the Disjoint Repair Group Property

This page was built for publication: Nearly Optimal Constructions of PIR and Batch Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4615354)