Document Open Access Logo

Error Correcting Codes for Uncompressed Messages

Authors Ofer Grossman, Justin Holmgren

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.43.pdf
  • Filesize: 0.59 MB
  • 18 pages

Document Identifiers

Author Details

Ofer Grossman
  • MIT, Cambridge, MA, USA
Justin Holmgren
  • NTT Research, Palo Alto, CA, USA

Funding

Work done in part while generously hosted by the Simons Institute.
  • Grossman, Ofer: Supported by a Fannie and John Hertz Foundation Fellowship and a NSF GRFP fellowship.
  • Holmgren, Justin: Work done in part while at Princeton University, supported by the Simons Collaboration on Algorithms and Geometry and National Science Foundation grant No. CCF-1714779.

Acknowledgements

We thank Elad Haramaty and Madhu Sudan for many very fruitful discussions in the early stages of this work. We also thank Venkat Guruswami and Lijie Chen for helpful discussions, and Shafi Goldwasser for her encouragement and her feedback on an earlier version of this work. We also thank anonymous reviewers for many useful comments on earlier versions of this work.

Cite AsGet BibTex

Ofer Grossman and Justin Holmgren. Error Correcting Codes for Uncompressed Messages. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.43

Abstract

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed. We show that in this setting, it is sub-optimal to use standard error correction. We consider a model where there is a set of "valid messages" which the sender may send that may not be efficiently compressible, but where it is possible for the receiver to recognize valid messages. In this model, we construct a (probabilistic) encoding procedure that achieves better tradeoffs between data rates and error-resilience (compared to just applying a standard error correcting code). Additionally, our techniques yield improved efficiently decodable (probabilistic) codes for fully compressed messages (the standard setting where the set of valid messages is all binary strings) in the high-rate regime.

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • Coding Theory
  • List Decoding

Metrics

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

Related Versions

Supplementary Materials

References

  1. Mohammad Bavarian, Dmitry Gavinsky, and Tsuyoshi Ito. On the role of shared randomness in simultaneous communication. In International Colloquium on Automata, Languages, and Programming, pages 150-162. Springer, 2014. Google Scholar
  2. E. L Blokh and Victor Zyablov. Linear concatenated codes. Nauka, 1982. Google Scholar
  3. Clément L Canonne, Venkatesan Guruswami, Raghu Meka, and Madhu Sudan. Communication with imperfectly shared randomness. IEEE Transactions on Information Theory, 63(10):6799-6818, 2017. Google Scholar
  4. Zitan Chen, Sidharth Jaggi, and Michael Langberg. The capacity of online (causal) q-ary error-erasure channels. IEEE Transactions on Information Theory, 65(6):3384-3411, 2019. Google Scholar
  5. Ilya Dumer, Mark S. Pinsker, and Vyacheslav V. Prelov. Epsilon-entropy of an ellipsoid in a hamming space. Probl. Inf. Transm., 38(1):1-15, 2002. Google Scholar
  6. Peter Elias. List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, MIT, 1957. Google Scholar
  7. Badih Ghazi, Ilan Komargodski, Pravesh Kothari, and Madhu Sudan. Communication with contextual uncertainty. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 2072-2085. SIAM, 2016. Google Scholar
  8. Badih Ghazi and Madhu Sudan. The power of shared randomness in uncertain communication. In ICALP, volume 80 of LIPIcs, pages 49:1-49:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  9. Oded Goldreich, Brendan Juba, and Madhu Sudan. A theory of goal-oriented communication. Journal of the ACM (JACM), 59(2):8, 2012. Google Scholar
  10. Oded Goldreich and Leonid A Levin. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 25-32. ACM, 1989. Google Scholar
  11. Ofer Grossman and Justin Holmgren. Error correcting codes for uncompressed messages. Electron. Colloquium Comput. Complex., 27:38, 2020. Google Scholar
  12. Venkatesan Guruswami. List decoding with side information. In IEEE Conference on Computational Complexity, page 300. IEEE Computer Society, 2003. Google Scholar
  13. Venkatesan Guruswami. Algorithmic results in list decoding. Theoretical Computer Science, 2(2):107-195, 2006. Google Scholar
  14. Venkatesan Guruswami and Atri Rudra. Better binary list decodable codes via multilevel concatenation. IEEE Transactions on Information Theory, 55(1):19-26, 2009. Google Scholar
  15. Venkatesan Guruswami and Adam Smith. Optimal rate code constructions for computationally simple channels. Journal of the ACM (JACM), 63(4):1-37, 2016. Google Scholar
  16. Elad Haramaty and Madhu Sudan. Deterministic compression with uncertain priors. Algorithmica, 76(3):630-653, 2016. Google Scholar
  17. Brett Hemenway, Noga Ron-Zewi, and Mary Wootters. Local list recovery of high-rate tensor codes & applications. In FOCS, pages 204-215. IEEE Computer Society, 2017. Google Scholar
  18. Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, and Madhu Sudan. Compression without a common prior: an information-theoretic justification for ambiguity in language. In ICS, pages 79-86. Tsinghua University Press, 2011. Google Scholar
  19. Eyal Kaplan, Moni Naor, and Omer Reingold. Derandomized constructions of k-wise (almost) independent permutations. Algorithmica, 55(1):113-133, 2009. Google Scholar
  20. Michael Langberg. Private codes or succinct random codes that are (almost) perfect. In FOCS, pages 325-334. IEEE Computer Society, 2004. Google Scholar
  21. Nathan Linial and Zur Luria. Chernoff’s inequality - a very elementary proof, 2014. URL: http://arxiv.org/abs/1403.7739.
  22. Atri Rudra. List decoding and property testing of error correcting codes. PhD thesis, University of Washington, 2007. Google Scholar
  23. Igal Sason. On refined versions of the Azuma-Hoeffding inequality with applications in information theory. arXiv preprint, 2011. URL: http://arxiv.org/abs/1111.1977.
  24. Madhu Sudan. Decoding of Reed Solomon codes beyond the error-correction bound. Journal of complexity, 13(1):180-193, 1997. Google Scholar
  25. Madhu Sudan. List decoding: Algorithms and applications. In IFIP International Conference on Theoretical Computer Science, pages 25-41. Springer, 2000. Google Scholar
  26. C. Thommesen. The existence of binary linear concatenated codes with Reed-Solomon outer codes which asymptotically meet the Gilbert-Varshamov bound. IEEE Transactions on Information Theory, 29(6):850-853, November 1983. URL: https://doi.org/10.1109/tit.1983.1056765.
  27. Mark N. Wegman and Larry Carter. New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci., 22(3):265-279, 1981. Google Scholar
  28. John M Wozencraft. List decoding. Quarterly Progress Report, 48:90-95, 1958. 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 Imprint Privacy Contact