On the Capacity of Locally Decodable Codes

DOI10.1109/TIT.2020.3014973MaRDI QIDQ5138836zbMATH OpenOpenAlexFDO

Authors Hua Sun, Syed A. Jafar

Publication date 4 December 2020

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

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

zbMATH Keywords

locally decodable code (LDC)Private Information RetrievalRepudiative Information Retrieval (RIR)

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Privacy of data (68P27) Source coding (94A29)

Abstract: A locally decodable code (LDC) maps $K$ source symbols, each of size $L_w$ bits, to $M$ coded symbols, each of size $L_x$ bits, such that each source symbol can be decoded from $NleqM$ coded symbols. A perfectly smooth LDC further requires that each coded symbol is uniformly accessed when we decode any one of the messages. The ratio $L_w/L_x$ is called the symbol rate of an LDC. The highest possible symbol rate for a class of LDCs is called the capacity of that class. It is shown that given $K,N$, the maximum value of capacity of perfectly smooth LDCs, maximized over all code lengths $M$, is $C^{\ast }=Nleft(1+1/N+1/N^2+cdots+1/N^{K-1}ight{)}^{-1}$. Furthermore, given $K,N$, the minimum code length $M$ for which the capacity of a perfectly smooth LDC is $C^{\ast }$ is shown to be $M=N^K$. Both of these results generalize to a broader class of LDCs, called universal LDCs. The results are then translated into the context of PIR${}_{max}$, i.e., Private Information Retrieval subject to maximum (rather than average) download cost metric. It is shown that the minimum upload cost of capacity achieving PIR${}_{max}$ schemes is $(K-1)logN$. The results also generalize to a variation of the PIR problem, known as Repudiative Information Retrieval (RIR).

Cited in

(8)

• On the locality of codeword symbols in non-linear codes
• Information-Theoretic Local Non-malleable Codes and Their Applications
• The Complexity of Local List Decoding
• scientific article; zbMATH DE number 1205988 (Why is no real title available?)
• Outlaw distributions and locally decodable codes
• Local asymptotic coding and the minimum description length
• Limitation on the Rate of Families of Locally Testable Codes
• Locally Decodable Codes

This page was built for publication: On the Capacity of Locally Decodable Codes

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