Explicit Constructions and Bounds for Batch Codes with Restricted Size of Reconstruction Sets

Preprint English OPEN
Thomas, Eldho K.; Skachek, Vitaly;
(2017)
  • Subject: Computer Science - Information Theory
    arxiv: Computer Science::Cryptography and Security

Linear batch codes and codes for private information retrieval (PIR) with a query size $t$ and a restricted size $r$ of the reconstruction sets are studied. New bounds on the parameters of such codes are derived for small values of $t$ or of $r$ by providing correspondi... View more
  • References (18)
    18 references, page 1 of 2

    [1] Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, “Batch codes and their applications”, Proc. of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, June 2004.

    [2] Z. Wang, H. M. Kiah and Y. Cassuto, “Optimal binary switch codes with small query size”, Proc. of the IEEE International Symposium on Information Theory (ISIT), Hong Kong, pp 636-640, June 2015.

    [3] Z. Wang, O. Shaked, Y. Cassuto and J. Bruck, “Codes for network switches”, Proc. of the IEEE International Symposium on Information Theory (ISIT), Istanbul, 2013.

    [4] Y.M. Chee, F. Gao, S. T. H. Teo and H. Zhang, “Combinatorial systematic switch codes”, Proc. of the IEEE International Symposium on Information Theory (ISIT), Hong Kong, China, pp. 241-245, 2015.

    [5] S. Bhattacharya, S. Ruj and B. Roy, “Combinatorial batch codes: a lower bound and optimal constructions”, Advances in Mathematics of Communications, vol. 6, no. 2, pp. 165-174, 2012.

    [6] R.A. Brualdi, K. Kiernan, S.A. Meyer and M.W. Schroeder, “Combinatorial batch codes and transversal matroids”, Advances in Mathematics of Communications, vol. 4, no. 3, pp. 419-431, 2010.

    [7] C. Bujtas and Z. Tuza, “Batch codes and their applications”, Electronic Notes in Discrete Mathematics, vol. 38, pp. 201-206, 2011.

    [8] A. Fazeli, A. Vardy, and E. Yaakobi, “PIR with low storage overhead: coding instead of replication”, arXiv:1505.06241, May 2015.

    [9] V. Cadambe and A. Mazumdar, “Bounds on the Size of Locally Recoverable Codes,” IEEE Transactions on Information Theory, vol. 61(11), pp. 5787-5794, Nov. 2015.

    [10] M. Forbes and S. Yekhanin, “On the locality of codeword sysmbols in non-linear codes”, Discrete Math, vol. 324, pp. 78-84, 2014.

  • Metrics
Share - Bookmark