Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes

Authors Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.37.pdf
  • Filesize: 484 kB
  • 15 pages

Document Identifiers

Author Details

Kuan Cheng
  • Department of Computer Science, Johns Hopkins University, USA
Zhengzhong Jin
  • Department of Computer Science, Johns Hopkins University, USA
Xin Li
  • Department of Computer Science, Johns Hopkins University, USA
Ke Wu
  • Department of Computer Science, Johns Hopkins University, USA

Acknowledgements

We thank an anonymous referee for catching an error in the previous version of this paper, and Bernhard Haeupler for very useful feedbacks.

Cite AsGet BibTex

Kuan Cheng, Zhengzhong Jin, Xin Li, and Ke Wu. Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.37

Abstract

Document exchange and error correcting codes are two fundamental problems regarding communications. In the first problem, Alice and Bob each holds a string, and the goal is for Alice to send a short sketch to Bob, so that Bob can recover Alice’s string. In the second problem, Alice sends a message with some redundant information to Bob through a channel that can add adversarial errors, and the goal is for Bob to correctly recover the message despite the errors. In both problems, an upper bound is placed on the number of errors between the two strings or that the channel can add, and a major goal is to minimize the size of the sketch or the redundant information. In this paper we focus on deterministic document exchange protocols and binary error correcting codes. Both problems have been studied extensively. In the case of Hamming errors (i.e., bit substitutions) and bit erasures, we have explicit constructions with asymptotically optimal parameters. However, other error types are still rather poorly understood. In a recent work [Kuan Cheng et al., 2018], the authors constructed explicit deterministic document exchange protocols and binary error correcting codes for edit errors with almost optimal parameters. Unfortunately, the constructions in [Kuan Cheng et al., 2018] do not work for other common errors such as block transpositions. In this paper, we generalize the constructions in [Kuan Cheng et al., 2018] to handle a much larger class of errors. These include bursts of insertions and deletions, as well as block transpositions. Specifically, we consider document exchange and error correcting codes where the total number of block insertions, block deletions, and block transpositions is at most k <= alpha n/log n for some constant 0<alpha<1. In addition, the total number of bits inserted and deleted by the first two kinds of operations is at most t <= beta n for some constant 0<beta<1, where n is the length of Alice’s string or message. We construct explicit, deterministic document exchange protocols with sketch size O((k log n +t) log^2 n/{k log n + t}) and explicit binary error correcting code with O(k log n log log log n+t) redundant bits. As a comparison, the information-theoretic optimum for both problems is Theta(k log n+t). As far as we know, previously there are no known explicit deterministic document exchange protocols in this case, and the best known binary code needs Omega(n) redundant bits even to correct just one block transposition [L. J. Schulman and D. Zuckerman, 1999].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Coding theory
Keywords
  • Deterministic document exchange
  • error correcting code
  • block edit error

Metrics

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

References

  1. Djamal Belazzougui. Efficient Deterministic Single Round Document Exchange for Edit Distance. CoRR, abs/1511.09229, 2015. URL: http://arxiv.org/abs/1511.09229.
  2. Djamal Belazzougui and Qin Zhang. Edit Distance: Sketching, Streaming, and Document Exchange. In Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science, pages 51-60. IEEE, 2016. Google Scholar
  3. J. Brakensiek, V. Guruswami, and S. Zbarsky. Efficient Low-Redundancy Codes for Correcting Multiple Deletions. IEEE Transactions on Information Theory, PP(99):1-1, 2017. URL: http://dx.doi.org/10.1109/TIT.2017.2746566.
  4. Boris Bukh and Venkatesan Guruswami. An improved bound on the fraction of correctable deletions. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1893-1901. ACM, 2016. Google Scholar
  5. Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký. Low Distortion Embedding from Edit to Hamming Distance using Coupling. In Proceedings of the 48th IEEE Annual Annual ACM SIGACT Symposium on Theory of Computing. ACM, 2016. Google Scholar
  6. K. Cheng, B. Haeupler, X. Li, A. Shahrasbi, and K. Wu. Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets. ArXiv e-prints, March 2018. URL: http://arxiv.org/abs/1803.03530.
  7. Kuan Cheng, Zhengzhong Jin, Xin Li, and Ke Wu. Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2018. Google Scholar
  8. Graham Cormode and S. Muthukrishnan. The string edit distance matching problem with moves. ACM Transactions on Algorithms, 3(1), 2007. Google Scholar
  9. Graham Cormode, Mike Paterson, Suleyman Cenk Sahinalp, and Uzi Vishkin. Communication complexity of document exchange. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 197-206. ACM, 2000. Google Scholar
  10. V. Guruswami and R. Li. Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 620-624, July 2016. URL: http://dx.doi.org/10.1109/ISIT.2016.7541373.
  11. V. Guruswami and C. Wang. Deletion Codes in the High-Noise and High-Rate Regimes. IEEE Transactions on Information Theory, 63(4):1961-1970, April 2017. URL: http://dx.doi.org/10.1109/TIT.2017.2659765.
  12. Bernhard Haeupler. Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.03604.
  13. Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings: codes for insertions and deletions approaching the Singleton bound. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 33-46. ACM, 2017. Google Scholar
  14. Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization Strings: Explicit Constructions, Local Decoding, and Applications. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing, 2018. Google Scholar
  15. Bernhard Haeupler, Amirbehshad Shahrasbi, and Ellen Vitercik. Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018. Google Scholar
  16. Tom Høholdt, Jacobus H Van Lint, and Ruud Pellikaan. Algebraic geometry codes. Handbook of coding theory, 1(Part 1):871-961, 1998. Google Scholar
  17. Utku Irmak, Svilen Mihaylov, and Torsten Suel. Improved single-round protocols for remote file synchronization. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 3, pages 1665-1676. IEEE, 2005. Google Scholar
  18. Hossein Jowhari. Efficient Communication Protocols for Deciding Edit Distance. In ESA, 2012. Google Scholar
  19. V. I. Levenshtein. Binary Codes Capable of Correcting Deletions, Insertions and Reversals. Soviet Physics Doklady, 10:707, February 1966. Google Scholar
  20. H. Mercier, V. K. Bhargava, and V. Tarokh. A survey of error-correcting codes for channels with symbol synchronization errors. IEEE Communications Surveys Tutorials, 12(1):87-96, First 2010. URL: http://dx.doi.org/10.1109/SURV.2010.020110.00079.
  21. A. Orlitsky. Interactive communication: balanced distributions, correlated files, and average-case complexity. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 228-238, October 1991. URL: http://dx.doi.org/10.1109/SFCS.1991.185373.
  22. G. M. Tenengol'ts R. R. Varshamov. Code Correcting Single Asymmetric Errors. Avtomat. i Telemekh, 26:288-292, 1965. Google Scholar
  23. L. J. Schulman and D. Zuckerman. Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE Transactions on Information Theory, 45(7):2552-2557, November 1999. URL: http://dx.doi.org/10.1109/18.796406.
  24. D Shapira and J. A. Storer. Edit distance with move operations. In Proceedings of the 13th Symposium on Combinatorial Pattern Matching, pages 85-98, 2002. 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