Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Gabriel Bathie, Tomasz Kociumaka, and Tatiana Starikovskaya. Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 10:1-10:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bathie_et_al:LIPIcs.ISAAC.2023.10, author = {Bathie, Gabriel and Kociumaka, Tomasz and Starikovskaya, Tatiana}, title = {{Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {10:1--10:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.10}, URN = {urn:nbn:de:0030-drops-193124}, doi = {10.4230/LIPIcs.ISAAC.2023.10}, annote = {Keywords: Approximate pattern matching, streaming algorithms, palindromes, squares} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Tomasz Kociumaka and Adam Polak. Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 72:1-72:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kociumaka_et_al:LIPIcs.ESA.2023.72, author = {Kociumaka, Tomasz and Polak, Adam}, title = {{Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {72:1--72:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.72}, URN = {urn:nbn:de:0030-drops-187257}, doi = {10.4230/LIPIcs.ESA.2023.72}, annote = {Keywords: Fine-grained complexity, graph algorithms, lower bounds, shortest paths} }
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Jarno N. Alanko, Elena Biagi, Simon J. Puglisi, and Jaakko Vuohtoniemi. Subset Wavelet Trees. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 4:1-4:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{alanko_et_al:LIPIcs.SEA.2023.4, author = {Alanko, Jarno N. and Biagi, Elena and Puglisi, Simon J. and Vuohtoniemi, Jaakko}, title = {{Subset Wavelet Trees}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.4}, URN = {urn:nbn:de:0030-drops-183549}, doi = {10.4230/LIPIcs.SEA.2023.4}, annote = {Keywords: degenerate strings, compressed data structures, succinct data structures, string processing, data structures, efficient algorithms} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Sudatta Bhattacharya and Michal Koucký. Streaming k-Edit Approximate Pattern Matching via String Decomposition. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 22:1-22:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bhattacharya_et_al:LIPIcs.ICALP.2023.22, author = {Bhattacharya, Sudatta and Kouck\'{y}, Michal}, title = {{Streaming k-Edit Approximate Pattern Matching via String Decomposition}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {22:1--22:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.22}, URN = {urn:nbn:de:0030-drops-180741}, doi = {10.4230/LIPIcs.ICALP.2023.22}, annote = {Keywords: Approximate pattern matching, edit distance, streaming algorithms} }
Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba. Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 15:1-15:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{iliopoulos_et_al:LIPIcs.CPM.2023.15, author = {Iliopoulos, Costas S. and Kociumaka, Tomasz and Radoszewski, Jakub and Rytter, Wojciech and Wale\'{n}, Tomasz and Zuba, Wiktor}, title = {{Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {15:1--15:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-276-1}, ISSN = {1868-8969}, year = {2023}, volume = {259}, editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.15}, URN = {urn:nbn:de:0030-drops-179697}, doi = {10.4230/LIPIcs.CPM.2023.15}, annote = {Keywords: cyclic cover, cyclic root, circular pattern matching, internal pattern matching} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Barna Saha. An Algorithmic Bridge Between Hamming and Levenshtein Distances. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 58:1-58:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{goldenberg_et_al:LIPIcs.ITCS.2023.58, author = {Goldenberg, Elazar and Kociumaka, Tomasz and Krauthgamer, Robert and Saha, Barna}, title = {{An Algorithmic Bridge Between Hamming and Levenshtein Distances}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {58:1--58:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.58}, URN = {urn:nbn:de:0030-drops-175615}, doi = {10.4230/LIPIcs.ITCS.2023.58}, annote = {Keywords: edit distance, Hamming distance, Longest Common Extension queries} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba. Approximate Circular Pattern Matching. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 35:1-35:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{charalampopoulos_et_al:LIPIcs.ESA.2022.35, author = {Charalampopoulos, Panagiotis and Kociumaka, Tomasz and Radoszewski, Jakub and Pissis, Solon P. and Rytter, Wojciech and Wale\'{n}, Tomasz and Zuba, Wiktor}, title = {{Approximate Circular Pattern Matching}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {35:1--35:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.35}, URN = {urn:nbn:de:0030-drops-169738}, doi = {10.4230/LIPIcs.ESA.2022.35}, annote = {Keywords: approximate circular pattern matching, Hamming distance, edit distance} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Debarati Das, Tomasz Kociumaka, and Barna Saha. Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 49:1-49:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{das_et_al:LIPIcs.ICALP.2022.49, author = {Das, Debarati and Kociumaka, Tomasz and Saha, Barna}, title = {{Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {49:1--49:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.49}, URN = {urn:nbn:de:0030-drops-163902}, doi = {10.4230/LIPIcs.ICALP.2022.49}, annote = {Keywords: Dyck Edit Distance, RNA Folding, String Algorithms} }
Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, and Przemysław Uznański. The Dynamic k-Mismatch Problem. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 18:1-18:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{clifford_et_al:LIPIcs.CPM.2022.18, author = {Clifford, Rapha\"{e}l and Gawrychowski, Pawe{\l} and Kociumaka, Tomasz and Martin, Daniel P. and Uzna\'{n}ski, Przemys{\l}aw}, title = {{The Dynamic k-Mismatch Problem}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {18:1--18:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.18}, URN = {urn:nbn:de:0030-drops-161454}, doi = {10.4230/LIPIcs.CPM.2022.18}, annote = {Keywords: Pattern matching, Hamming distance, dynamic algorithms} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski. Faster Algorithms for Longest Common Substring. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 30:1-30:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{charalampopoulos_et_al:LIPIcs.ESA.2021.30, author = {Charalampopoulos, Panagiotis and Kociumaka, Tomasz and Pissis, Solon P. and Radoszewski, Jakub}, title = {{Faster Algorithms for Longest Common Substring}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {30:1--30:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.30}, URN = {urn:nbn:de:0030-drops-146114}, doi = {10.4230/LIPIcs.ESA.2021.30}, annote = {Keywords: longest common substring, k mismatches, wavelet tree} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Grigorios Loukides and Solon P. Pissis. Bidirectional String Anchors: A New String Sampling Mechanism. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 64:1-64:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{loukides_et_al:LIPIcs.ESA.2021.64, author = {Loukides, Grigorios and Pissis, Solon P.}, title = {{Bidirectional String Anchors: A New String Sampling Mechanism}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {64:1--64:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.64}, URN = {urn:nbn:de:0030-drops-146456}, doi = {10.4230/LIPIcs.ESA.2021.64}, annote = {Keywords: string algorithms, string sampling, text indexing, top-K similarity search} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba. Hardness of Detecting Abelian and Additive Square Factors in Strings. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 77:1-77:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{radoszewski_et_al:LIPIcs.ESA.2021.77, author = {Radoszewski, Jakub and Rytter, Wojciech and Straszy\'{n}ski, Juliusz and Wale\'{n}, Tomasz and Zuba, Wiktor}, title = {{Hardness of Detecting Abelian and Additive Square Factors in Strings}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {77:1--77:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.77}, URN = {urn:nbn:de:0030-drops-146581}, doi = {10.4230/LIPIcs.ESA.2021.77}, annote = {Keywords: Abelian square, additive square, 3SUM problem} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Barna Saha. Sublinear Algorithms for Edit Distance (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 5:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{saha:LIPIcs.MFCS.2021.5, author = {Saha, Barna}, title = {{Sublinear Algorithms for Edit Distance}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {5:1--5:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.5}, URN = {urn:nbn:de:0030-drops-144452}, doi = {10.4230/LIPIcs.MFCS.2021.5}, annote = {Keywords: Edit distance, sublinear algorithms, string processing} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Amihood Amir, Itai Boneh, and Eitan Kondratovsky. The k-Mappability Problem Revisited. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 5:1-5:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{amir_et_al:LIPIcs.CPM.2021.5, author = {Amir, Amihood and Boneh, Itai and Kondratovsky, Eitan}, title = {{The k-Mappability Problem Revisited}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.5}, URN = {urn:nbn:de:0030-drops-139566}, doi = {10.4230/LIPIcs.CPM.2021.5}, annote = {Keywords: Pattern Matching, Hamming Distance, Suffix Tree, Suffix Array} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka, and Florian Kurpicz. Practical Performance of Space Efficient Data Structures for Longest Common Extensions. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 39:1-39:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{dinklage_et_al:LIPIcs.ESA.2020.39, author = {Dinklage, Patrick and Fischer, Johannes and Herlez, Alexander and Kociumaka, Tomasz and Kurpicz, Florian}, title = {{Practical Performance of Space Efficient Data Structures for Longest Common Extensions}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {39:1--39:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.39}, URN = {urn:nbn:de:0030-drops-129050}, doi = {10.4230/LIPIcs.ESA.2020.39}, annote = {Keywords: text indexing, longest common prefix, space efficient data structures} }
Feedback for Dagstuhl Publishing