This seminar is offered for students enrolled in the Mathematics Master as module S4C1 as well as students enrolled in the Computer Science Master as module MA-INF 1205. The seminar is organized and held by Prof. Dr. Anne Driemel.

The goal of the seminar is for each participant to:

• Study a scientific paper (see references below)
• Present the main ideas of the paper in a talk (45 Minutes)
• Participate in discussions on the topic of the seminar
• Submit a written report (in own words) (10 pages)

The first preparation meeting for the seminar will take place on Friday 19 July 2024, at 2 pm in room 2.050 (Informatik V, 2. OG) . The meeting room is located in the computer science building at Friedrich Hirzebruch Allee 8. The assignment of topics and the schedule of talks will be decided after the first meeting. If you are interested to participate in the seminar and want to receive updates, please contact Prof. Dr. Anne Driemel.

eCampus Link: https://ecampus.uni-bonn.de/goto_ecampus_crs_3461253.html

Computing the Fréchet distance between two polygonal curves takes quadratic time in the number of edges and this is known to be optimal up to subpolynomial factors under the Strong Exponential Time Hypothesis. The same holds for the Edit Distance of strings and the Dynamic Time Warping distance. In this seminar we will recapitulate these lower bounds and subsequently focus on modern approximation algorithms for these problems that run in strongly subquadratic time. Special focus is given to the new subquadratic constant-factor approximation algorithm for the Edit distance. For the other distance measures such approximation algorithms are still out of reach. We will discuss the techniques leading to the current state of the art and compare between the distance measures.

1. Andoni, Alexandr, and Negev Shekel Nosatzki. “Edit Distance in Near-Linear Time: It’s a Constant Factor.” In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 990–1001, 2020. https://doi.org/10.1109/FOCS46700.2020.00096.
2. Andoni, Alexandr, and Krzysztof Onak. “Approximating Edit Distance in Near-Linear Time.” In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, 199–204. STOC ’09. New York, NY, USA: Association for Computing Machinery, 2009. https://doi.org/10.1145/1536414.1536444.
3. Chakraborty, Diptarka, Debarati Das, Elazar Goldenberg, Michal Koucký, and Michael Saks. “Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time.” J. ACM 67, no. 6 (October 29, 2020): 36:1-36:22. https://doi.org/10.1145/3422823.
4. Chan, Timothy M., and Zahed Rahmati. “An Improved Approximation Algorithm for the Discrete Fréchet Distance.” Information Processing Letters 138 (October 1, 2018): 72–74. https://doi.org/10.1016/j.ipl.2018.06.011.
5. Bringmann, Karl. “Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails.” In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 661–70. FOCS ’14. USA: IEEE Computer Society, 2014. https://doi.org/10.1109/FOCS.2014.76.
6. Bringmann, Karl, and Marvin Künnemann. “Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.” In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 79–97. IEEE, 2015. https://ieeexplore.ieee.org/abstract/document/7354389/.
7. Driemel, Anne, Sariel Har-Peled, and Carola Wenk. “Approximating the Fréchet Distance for Realistic Curves in near Linear Time.” In Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, 365–74. Snowbird Utah USA: ACM, 2010. https://doi.org/10.1145/1810959.1811019.
8. Horst, Thijs van der, and Tim Ophelders. “Faster Fr\’echet Distance Approximation through Truncated Smoothing.” arXiv, January 26, 2024. https://doi.org/10.48550/arXiv.2401.14815.
9. Landau, Gad M., and Uzi Vishkin. “Fast String Matching with k Differences.” Journal of Computer and System Sciences 37, no. 1 (August 1, 1988): 63–78. https://doi.org/10.1016/0022-0000(88)90045-1.
10. Ostrovsky, Rafail, and Yuval Rabani. “Low Distortion Embeddings for Edit Distance.” J. ACM 54, no. 5 (October 1, 2007): 23-es. https://doi.org/10.1145/1284320.1284322.
11. Xi, Zoe, and William Kuszmaul. “Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings.” arXiv, July 2, 2022. https://doi.org/10.48550/arXiv.2207.00915.
12. Ying, Rex, Jiangwei Pan, Kyle Fox, and Pankaj K. Agarwal. “A Simple Efficient Approximation Algorithm for Dynamic Time Warping.” In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 1–10. SIGSPATIAL ’16. New York, NY, USA: Association for Computing Machinery, 2016. https://doi.org/10.1145/2996913.2996954.
13. Brakensiek, Joshua, and Aviad Rubinstein. “Constant-Factor Approximation of near-Linear Edit Distance in near-Linear Time.” In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 685–98. STOC 2020. New York, NY, USA: Association for Computing Machinery, 2020. https://doi.org/10.1145/3357713.3384282.
14. Colombe, Connor, and Kyle Fox. “Approximating the (Continuous) Fréchet Distance.” In DROPS-IDN/v2/Document/10.4230/LIPIcs.SoCG.2021.26. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.26.
15. Horst, Thijs van der, Marc van Kreveld, Tim Ophelders, and Bettina Speckmann. “A Subquadratic Nε-Approximation for the Continuous Fréchet Distance.” In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1759–76. Proceedings. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/1.9781611977554.ch67.
16. Koucký, Michal, and Michael Saks. “Constant Factor Approximations to Edit Distance on Far Input Pairs in Nearly Linear Time.” In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 699–712. STOC 2020. New York, NY, USA: Association for Computing Machinery, 2020. https://doi.org/10.1145/3357713.3384307.