Batch Codes and Their Applications
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Abstract: A batch code encodes a string x of length n into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket. Batch codes can be viewed as relaxing several combinatorial objects, including expanders and locally decodable codes.
We initiate the study of these codes by presenting some constructions, connections with other problems, and lower bounds. We also demonstrate the usefulness of batch codes by presenting two types of applications: trading maximal load for storage in certain load-balancing scenarios, and amortizing the computational cost of private information retrieval (PIR) and related cryptographic protocols.
comment: Appeared In Proceedings of ACM Symposium on Theory of Computing (STOC-2004)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |