Document Open Access Logo

Locality via Partially Lifted Codes

Authors S. Luna Frank-Fischer, Venkatesan Guruswami, Mary Wootters

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2017.43.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Subject Classification

Keywords
  • Error correcting codes
  • locality
  • lifted codes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

In error-correcting codes, locality refers to several different ways of quantifying how easily a small amount of information can be recovered from encoded data.  In this work, we study a notion of locality called the s-Disjoint-Repair-Group Property (s-DRGP).  This notion can interpolate between two very different settings in coding theory: that of Locally Correctable Codes (LCCs) when s is large - a very strong guarantee - and Locally Recoverable Codes (LRCs) when s is small - a relatively weaker guarantee.  This motivates the study of the s-DRGP for intermediate s, which is the focus of our paper.  We construct codes in this parameter regime which have a higher rate than previously known codes.  Our construction is based on a novel variant of the lifted codes of Guo, Kopparty and Sudan.  Beyond the results on the s-DRGP, we hope that our construction is of independent interest, and will find uses elsewhere.

Cite As Get BibTex

S. Luna Frank-Fischer, Venkatesan Guruswami, and Mary Wootters. Locality via Partially Lifted Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.43

Author Details

S. Luna Frank-Fischer
Venkatesan Guruswami
Mary Wootters

References

  1. Hilal Asi and Eitan Yaakobi. Nearly optimal constructions of PIR and batch codes. CoRR, abs/1701.07206, 2017. URL: http://arxiv.org/abs/1701.07206.
  2. E. F. Assmus and J. D. Key. Polynomial codes and finite geometries. Handbook of coding theory, 2(part 2):1269-1343, 1998. Google Scholar
  3. Megasthenis Asteris and Alexandros G. Dimakis. Repairable fountain codes. IEEE Journal on Selected Areas in Communications, 32(5):1037-1047, 2014. Google Scholar
  4. Eli Ben-Sasson and Madhu Sudan. Limits on the rate of locally testable affine-invariant codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 412-423. Springer, 2011. Google Scholar
  5. Arnab Bhattacharyya and Sivakanth Gopi. Lower bounds for constant query affine-invariant LCCs and LTCs. In Proceedings of the 31st Conference on Computational Complexity, volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.12.
  6. S. Blackburn and T. Etzion. PIR Array Codes with Optimal PIR Rate. CoRR, abs/1607.00235, 2016. URL: http://arxiv.org/abs/1607.00235.
  7. Alexandros G Dimakis, Anna Gál, Ankit Singh Rawat, and Zhao Song. Batch codes through dense graphs without short cycles. arXiv preprint arXiv:1410.2920, 2014. Google Scholar
  8. Arman Fazeli, Alexander Vardy, and Eitan Yaakobi. Codes for distributed PIR with low storage overhead. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 2852-2856. IEEE, 2015. Google Scholar
  9. S Luna Frank-Fischer, Venkatesan Guruswami, and Mary Wootters. Locality via partially lifted codes. arXiv preprint arXiv:1704.08627, 2017. Google Scholar
  10. Parikshit Gopalan, Cheng Huang, Huseyin Simitci, and Sergey Yekhanin. On the locality of codeword symbols. IEEE Transactions on Information Theory, 58(11):6925-6934, 2012. Google Scholar
  11. Alan Guo and Swastik Kopparty. List-decoding algorithms for lifted codes. CoRR, abs/1412.0305, 2014. URL: http://arxiv.org/abs/1412.0305.
  12. Alan Guo, Swastik Kopparty, and Madhu Sudan. New affine-invariant codes from lifting. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, ITCS'13, pages 529-540, New York, NY, USA, 2013. ACM. URL: http://arxiv.org/abs/1208.5413, http://arxiv.org/abs/1208.5413, URL: http://dx.doi.org/10.1145/2422436.2422494.
  13. Brett Hemenway, Rafail Ostrovsky, and Mary Wootters. Local Correctability of Expander Codes. In ICALP, LNCS. Springer, April 2013. URL: http://arxiv.org/abs/1304.8129.
  14. Cheng Huang, Minghua Chen, and Jin Li. Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems. ACM Transactions on Storage (TOS), 9(1):3, 2013. Google Scholar
  15. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Batch codes and their applications. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 262-271. ACM, 2004. Google Scholar
  16. Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In STOC'00: Proceedings of the 32nd Annual Symposium on the Theory of Computing, pages 80-86, 2000. Google Scholar
  17. S. Kopparty, S. Saraf, and S. Yekhanin. High-rate codes with sublinear-time decoding. In Proceedings of the 43rd annual ACM symposium on Theory of computing, pages 167-176. ACM, 2011. Google Scholar
  18. Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 202-215. ACM, 2016. Google Scholar
  19. Shu Lin and Daniel J Costello. Error control coding. Pearson Education India, 2004. Google Scholar
  20. Sankeerth Rao and Alexander Vardy. Lower bound on the redundancy of PIR codes. CoRR, abs/1605.01869, 2016. URL: http://arxiv.org/abs/1605.01869.
  21. Ankit Singh Rawat, Dimitris S. Papailiopoulos, Alexandros G. Dimakis, and Sriram Vishwanath. Locality and availability in distributed storage. In 2014 IEEE International Symposium on Information Theory, pages 681-685. IEEE, 2014. Google Scholar
  22. I. Reed. A class of multiple-error-correcting codes and the decoding scheme. Information Theory, Transactions of the IRE Professional Group on, 4(4):38-49, September 1954. Google Scholar
  23. Maheswaran Sathiamoorthy, Megasthenis Asteris, Dimitris Papailiopoulos, Alexandros G Dimakis, Ramkumar Vadali, Scott Chen, and Dhruba Borthakur. Xoring elephants: Novel erasure codes for big data. In Proceedings of the VLDB Endowment, volume 6, pages 325-336. VLDB Endowment, 2013. Google Scholar
  24. Vitaly Skachek. Batch and PIR codes and their connections to locally-repairable codes. CoRR, abs/1611.09914, 2016. URL: http://arxiv.org/abs/1611.09914.
  25. Itzhak Tamo and Alexander Barg. Bounds on locally recoverable codes with multiple recovering sets. In 2014 IEEE International Symposium on Information Theory, pages 691-695. IEEE, 2014. Google Scholar
  26. Itzhak Tamo and Alexander Barg. A family of optimal locally recoverable codes. IEEE Transactions on Information Theory, 60(8):4661-4676, 2014. Google Scholar
  27. Itzhak Tamo, Alexander Barg, and Alexey Frolov. Bounds on the parameters of locally recoverable codes. IEEE Transactions on Information Theory, 62(6):3070-3083, 2016. Google Scholar
  28. Anyu Wang and Zhifang Zhang. Repair locality with multiple erasure tolerance. IEEE Transactions on Information Theory, 60(11):6979-6987, 2014. Google Scholar
  29. David P. Woodruff. A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field, pages 766-779. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. Google Scholar
  30. Sergey Yekhanin. Locally Decodable Codes. Foundations and Trends in Theoretical Computer Science, 2010. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact