Document Open Access Logo

Improved List-Decodability of Random Linear Binary Codes

Authors Ray Li, Mary Wootters

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.50.pdf
  • Filesize: 0.51 MB
  • 19 pages

Document Identifiers

Author Details

Ray Li
  • Department of Computer Science, Stanford University, USA
Mary Wootters
  • Departments of Computer Science and Electrical Engineering, Stanford University, USA

Funding

  • Li, Ray: Research supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE - 1656518.

Cite As Get BibTex

Ray Li and Mary Wootters. Improved List-Decodability of Random Linear Binary Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.50

Abstract

There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate 1 - H(p) - epsilon is (p,O(1/epsilon))-list-decodable with high probability. In this work, we show that such codes are (p, H(p)/epsilon + 2)-list-decodable with high probability, for any p in (0, 1/2) and epsilon > 0. In addition to improving the constant in known list-size bounds, our argument - which is quite simple - works simultaneously for all values of p, while previous works obtaining L = O(1/epsilon) patched together different arguments to cover different parameter regimes.
Our approach is to strengthen an existential argument of (Guruswami, Håstad, Sudan and Zuckerman, IEEE Trans. IT, 2002) to hold with high probability. To complement our upper bound for random linear binary codes, we also improve an argument of (Guruswami, Narayanan, IEEE Trans. IT, 2014) to obtain a tight lower bound of 1/epsilon on the list size of uniformly random binary codes; this implies that random linear binary codes are in fact more list-decodable than uniformly random binary codes, in the sense that the list sizes are strictly smaller.
To demonstrate the applicability of these techniques, we use them to (a) obtain more information about the distribution of list sizes of random linear binary codes and (b) to prove a similar result for random linear rank-metric codes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • List-decoding
  • Random linear codes
  • Rank-metric codes

Metrics

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

Related Versions

References

  1. Volodia M. Blinovsky. Bounds for codes in the case of list decoding of finite volume. Problems of Information Transmission, 22(1):7–19, 1986. Google Scholar
  2. Mahdi Cheraghchi, Venkatesan Guruswami, and Ameya Velingker. Restricted isometry of Fourier matrices and list decodability of random linear codes. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 432-442. ACM-SIAM, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.31.
  3. Philippe Delsarte. Bilinear forms over a finite field, with applications to coding theory. Journal of Combinatorial Theory, Series A, 25(3):226-241, 1978. Google Scholar
  4. Yang Ding. On list-decodability of random rank metric codes and subspace codes. IEEE Trans. Information Theory, 61(1):51-59, 2015. URL: http://dx.doi.org/10.1109/TIT.2014.2371915.
  5. Zeev Dvir and Shachar Lovett. Subspace evasive sets. In Proceedings of the Forty-Fourth annual ACM Symposium on Theory of Computing (STOC), pages 351-358. ACM, 2012. Google Scholar
  6. Peter Elias. List decoding for noisy channels. Wescon Convention Record, Part 2, pages 94-104, 1957. Google Scholar
  7. Peter Elias. Error-correcting codes for list decoding. IEEE Trans. Information Theory, 37(1):5-12, 1991. Google Scholar
  8. Ernst M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov. Ideals over a non-commutative ring and their applications in cryptology. In Proceedings of Advances in Cryptology - EUROCRYPT '91, Workshop on the Theory and Application of of Cryptographic Techniques, pages 482-489, 1991. URL: http://dx.doi.org/10.1007/3-540-46416-6_41.
  9. Ernst Mukhamedovich Gabidulin. Theory of codes with maximum rank distance. Problemy Peredachi Informatsii, 21(1):3-16, 1985. Google Scholar
  10. Maximilien Gadouleau and Zhiyuan Yan. On the decoder error probability of bounded rank-distance decoders for maximum rank-distance codes. IEEE Trans. Information Theory, 54(7):3202-3206, 2008. URL: http://dx.doi.org/10.1109/TIT.2008.924697.
  11. Venkatesan Guruswami. List decoding of binary codes-a brief survey of some recent results. In Proceedings of Coding and Cryptology, Second International Workshop (IWCC), pages 97-106, 2009. URL: http://dx.doi.org/10.1007/978-3-642-01877-0_10.
  12. Venkatesan Guruswami, Johan Håstad, and Swastik Kopparty. On the list-decodability of random linear codes. IEEE Trans. Information Theory, 57(2):718-725, 2011. URL: http://dx.doi.org/10.1109/TIT.2010.2095170.
  13. Venkatesan Guruswami, Johan Håstad, Madhu Sudan, and David Zuckerman. Combinatorial bounds for list decoding. IEEE Trans. Information Theory, 48(5):1021-1034, 2002. URL: http://dx.doi.org/10.1109/18.995539.
  14. Venkatesan Guruswami and Piotr Indyk. Efficiently decodable codes meeting gilbert-varshamov bound for low rates. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 756-757. Society for Industrial and Applied Mathematics, 2004. Google Scholar
  15. Venkatesan Guruswami and Srivatsan Narayanan. Combinatorial limitations of average-radius list-decoding. IEEE Trans. Information Theory, 60(10):5827-5842, 2014. URL: http://dx.doi.org/10.1109/TIT.2014.2343224.
  16. Venkatesan Guruswami and Nicolas Resch. On the list-decodability of random linear rank-metric codes. arXiv preprint arXiv:1710.11516, 2017. Google Scholar
  17. Venkatesan Guruswami and Atri Rudra. Concatenated codes can achieve list-decoding capacity. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 258-267, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347111.
  18. Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Trans. Information Theory, 54(1):135-150, 2008. Google Scholar
  19. Venkatesan Guruswami and Salil Vadhan. A lower bound on list size for list decoding. In Chandra Chekuri, Klaus Jansen, José D. P. Rolim, and Luca Trevisan, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 318-329, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  20. Venkatesan Guruswami, Carol Wang, and Chaoping Xing. Explicit list-decodable rank-metric and subspace codes via subspace designs. IEEE Trans. Information Theory, 62(5):2707-2718, 2016. Google Scholar
  21. Venkatesan Guruswami and Chaoping Xing. Folded codes from function field towers and improved optimal rate list decoding. In Proceedings of the Forty-Fourth annual ACM Symposium on Theory of Computing (STOC), pages 339-350. ACM, 2012. Google Scholar
  22. Venkatesan Guruswami and Chaoping Xing. List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound. In Proceedings of the Forty-Fifth annual ACM Symposium on Theory of Computing (STOC), pages 843-852. ACM, 2013. Google Scholar
  23. Brett Hemenway, Noga Ron-Zewi, and Mary Wootters. Local list recovery of high-rate tensor codes &applications. In 58th Annual IEEE Symposium on Foundations of Computer Science, 2017. Google Scholar
  24. Brett Hemenway and Mary Wootters. Linear-time list recovery of high-rate expander codes. In International Colloquium on Automata, Languages, and Programming, pages 701-712. Springer, 2015. Google Scholar
  25. Ralf Koetter and Frank R Kschischang. Coding for errors and erasures in random network coding. IEEE Trans. Information Theory, 54(8):3579-3591, 2008. Google Scholar
  26. Ray Li and Mary Wootters. Improve list-decodability of random linear binary code. CoRR, abs/1801.07839, 2018. URL: http://arxiv.org/abs/1801.07839.
  27. Pierre Loidreau. Designing a rank metric based mceliece cryptosystem. In Proceedings of the Post-Quantum Cryptography, Third International Workshop on Post-Quantum Cryptography, (PQCrypto), pages 142-152, 2010. URL: http://dx.doi.org/10.1007/978-3-642-12929-2_11.
  28. Pierre Loidreau. A new rank metric codes based encryption scheme. In Proceedings of the Post-Quantum Cryptography, 8th International Workshop on Post-Quantum Cryptography, (PQCrypto), pages 3-17, 2017. URL: http://dx.doi.org/10.1007/978-3-319-59879-6_1.
  29. Hsiao-feng Lu and P. Vijay Kumar. A unified construction of space-time codes with optimal rate-diversity tradeoff. IEEE Trans. Information Theory, 51(5):1709-1730, 2005. URL: http://dx.doi.org/10.1109/TIT.2005.846403.
  30. P. Lusina, Ernst M. Gabidulin, and Martin Bossert. Maximum rank distance codes as space-time codes. IEEE Trans. Information Theory, 49(10):2757-2760, 2003. URL: http://dx.doi.org/10.1109/TIT.2003.818023.
  31. Ron M. Roth. Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Information Theory, 37(2):328-336, 1991. URL: http://dx.doi.org/10.1109/18.75248.
  32. Atri Rudra. Limits to list decoding of random codes. IEEE Trans. Information Theory, 57(3):1398-1408, 2011. URL: http://dx.doi.org/10.1109/TIT.2010.2054750.
  33. Atri Rudra and Steve Uurtamo. Two theorems on list decoding. In Maria Serna, Ronen Shaltiel, Klaus Jansen, and José Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 696-709, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  34. Atri Rudra and Mary Wootters. Every list-decodable code for high noise has abundant near-optimal rate puncturings. In Proceedings of the Forty-Sixth annual ACM Symposium on Theory of Computing (STOC), pages 764-773. ACM, 2014. Google Scholar
  35. Atri Rudra and Mary Wootters. It'll probably work out: Improved list-decoding through random operations. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS), pages 287-296. ACM, 2015. URL: http://dx.doi.org/10.1145/2688073.2688092.
  36. Atri Rudra and Mary Wootters. Average-radius list-recovery of random linear codes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM-SIAM, 2018. Google Scholar
  37. Natalia Silberstein, Ankit Singh Rawat, O Ozan Koyluoglu, and Sriram Vishwanath. Optimal locally repairable codes via rank-metric codes. In Proceedings of the 2013 IEEE International Symposium on Information Theory (ISIT), pages 1819-1823. IEEE, 2013. Google Scholar
  38. Natalia Silberstein, Ankit Singh Rawat, and Sriram Vishwanath. Error resilience in distributed storage via rank-metric codes. In Proceedings of the 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1150-1157. IEEE, 2012. Google Scholar
  39. Danilo Silva, Frank R Kschischang, and Ralf Koetter. A rank-metric approach to error control in random network coding. IEEE Trans. Information Theory, 54(9):3951-3967, 2008. Google Scholar
  40. Madhu Sudan. List decoding: algorithms and applications. SIGACT News, 31(1):16-27, 2000. URL: http://dx.doi.org/10.1145/346048.346049.
  41. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. URL: http://dx.doi.org/10.1561/0400000010.
  42. Antonia Wachter-Zeh. Bounds on list decoding of rank-metric codes. IEEE Trans. Information Theory, 59(11):7268-7277, 2013. Google Scholar
  43. Mary Wootters. On the list decodability of random linear codes with large error rates. In Proceedings of the Forty-Fifth Symposium on Theory of Computing Conference (STOC), pages 853-860, 2013. URL: http://dx.doi.org/10.1145/2488608.2488716.
  44. Jack Wozencraft. List decoding. Quarter Progress Report, 48:90-95, 1958. Google Scholar
  45. Victor Vasilievich Zyablov and Mark Semenovich Pinsker. List concatenated decoding. Problemy Peredachi Informatsii, 17(4):29-33, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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