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 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Petr Gregor, Arturo Merino, and Torsten Mütze. The Hamilton Compression of Highly Symmetric Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 54:1-54:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gregor_et_al:LIPIcs.MFCS.2022.54, author = {Gregor, Petr and Merino, Arturo and M\"{u}tze, Torsten}, title = {{The Hamilton Compression of Highly Symmetric Graphs}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {54:1--54:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.54}, URN = {urn:nbn:de:0030-drops-168529}, doi = {10.4230/LIPIcs.MFCS.2022.54}, annote = {Keywords: Hamilton cycle, Gray code, hypercube, permutahedron, Johnson graph, Cayley graph, abelian group, vertex-transitive} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Pavel Dvořák, Michal Koucký, Karel Král, and Veronika Slívová. Data Structures Lower Bounds and Popular Conjectures. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 39:1-39:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{dvorak_et_al:LIPIcs.ESA.2021.39, author = {Dvo\v{r}\'{a}k, Pavel and Kouck\'{y}, Michal and Kr\'{a}l, Karel and Sl{\'\i}vov\'{a}, Veronika}, title = {{Data Structures Lower Bounds and Popular Conjectures}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {39:1--39:15}, 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.39}, URN = {urn:nbn:de:0030-drops-146207}, doi = {10.4230/LIPIcs.ESA.2021.39}, annote = {Keywords: Data structures, Circuits, Lower bounds, Network Coding Conjecture} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Michal Koucký and Karel Král. Sorting Short Integers. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 88:1-88:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{koucky_et_al:LIPIcs.ICALP.2021.88, author = {Kouck\'{y}, Michal and Kr\'{a}l, Karel}, title = {{Sorting Short Integers}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {88:1--88:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.88}, URN = {urn:nbn:de:0030-drops-141577}, doi = {10.4230/LIPIcs.ICALP.2021.88}, annote = {Keywords: sorting, small integers, boolean circuits} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Zhenjian Lu and Igor C. Oliveira. An Efficient Coding Theorem via Probabilistic Representations and Its Applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 94:1-94:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{lu_et_al:LIPIcs.ICALP.2021.94, author = {Lu, Zhenjian and Oliveira, Igor C.}, title = {{An Efficient Coding Theorem via Probabilistic Representations and Its Applications}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {94:1--94:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.94}, URN = {urn:nbn:de:0030-drops-141630}, doi = {10.4230/LIPIcs.ICALP.2021.94}, annote = {Keywords: computational complexity, randomized algorithms, Kolmogorov complexity} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Michal Koucký. Computing Edit Distance (Invited Talk). In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{koucky:LIPIcs.CPM.2021.2, author = {Kouck\'{y}, Michal}, title = {{Computing Edit Distance}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {2:1--2:1}, 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.2}, URN = {urn:nbn:de:0030-drops-139534}, doi = {10.4230/LIPIcs.CPM.2021.2}, annote = {Keywords: edit distance, streaming algorithms, approximation algorithms, sketching} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Pavel Dvořák and Michal Koucký. Barrington Plays Cards: The Complexity of Card-Based Protocols. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 26:1-26:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{dvorak_et_al:LIPIcs.STACS.2021.26, author = {Dvo\v{r}\'{a}k, Pavel and Kouck\'{y}, Michal}, title = {{Barrington Plays Cards: The Complexity of Card-Based Protocols}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {26:1--26:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.26}, URN = {urn:nbn:de:0030-drops-136715}, doi = {10.4230/LIPIcs.STACS.2021.26}, annote = {Keywords: Efficient card-based protocol, Branching program, Turing machine} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Pavel Dvořák and Bruno Loff. Lower Bounds for Semi-adaptive Data Structures via Corruption. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 20:1-20:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{dvorak_et_al:LIPIcs.FSTTCS.2020.20, author = {Dvo\v{r}\'{a}k, Pavel and Loff, Bruno}, title = {{Lower Bounds for Semi-adaptive Data Structures via Corruption}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {20:1--20:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.20}, URN = {urn:nbn:de:0030-drops-132617}, doi = {10.4230/LIPIcs.FSTTCS.2020.20}, annote = {Keywords: semi-adaptive dynamic data structure, polynomial lower bound, corruption bound, information theory} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf. Improved Bounds on Fourier Entropy and Min-Entropy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 45:1-45:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{arunachalam_et_al:LIPIcs.STACS.2020.45, author = {Arunachalam, Srinivasan and Chakraborty, Sourav and Kouck\'{y}, Michal and Saurabh, Nitin and de Wolf, Ronald}, title = {{Improved Bounds on Fourier Entropy and Min-Entropy}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {45:1--45:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.45}, URN = {urn:nbn:de:0030-drops-119062}, doi = {10.4230/LIPIcs.STACS.2020.45}, annote = {Keywords: Fourier analysis of Boolean functions, FEI conjecture, query complexity, polynomial approximation, approximate degree, certificate complexity} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Shuichi Hirahara. Unexpected Power of Random Strings. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 41:1-41:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{hirahara:LIPIcs.ITCS.2020.41, author = {Hirahara, Shuichi}, title = {{Unexpected Power of Random Strings}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {41:1--41:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.41}, URN = {urn:nbn:de:0030-drops-117262}, doi = {10.4230/LIPIcs.ITCS.2020.41}, annote = {Keywords: Kolmogorov-Randomness, Nonadaptive Reduction, BPP, Symmetric Alternation} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Diptarka Chakraborty, Debarati Das, and Michal Koucký. Approximate Online Pattern Matching in Sublinear Time. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 10:1-10:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2019.10, author = {Chakraborty, Diptarka and Das, Debarati and Kouck\'{y}, Michal}, title = {{Approximate Online Pattern Matching in Sublinear Time}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.10}, URN = {urn:nbn:de:0030-drops-115726}, doi = {10.4230/LIPIcs.FSTTCS.2019.10}, annote = {Keywords: Approximate Pattern Matching, Online Pattern Matching, Edit Distance, Sublinear Algorithm, Streaming Algorithm} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. Unambiguous Catalytic Computation. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 16:1-16:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{gupta_et_al:LIPIcs.FSTTCS.2019.16, author = {Gupta, Chetan and Jain, Rahul and Sharma, Vimal Raj and Tewari, Raghunath}, title = {{Unambiguous Catalytic Computation}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {16:1--16:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.16}, URN = {urn:nbn:de:0030-drops-115782}, doi = {10.4230/LIPIcs.FSTTCS.2019.16}, annote = {Keywords: Catalytic computation, Logspace, Reinhardt-Allender} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Igor Carboni Oliveira. Randomness and Intractability in Kolmogorov Complexity. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 32:1-32:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{oliveira:LIPIcs.ICALP.2019.32, author = {Oliveira, Igor Carboni}, title = {{Randomness and Intractability in Kolmogorov Complexity}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {32:1--32:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.32}, URN = {urn:nbn:de:0030-drops-106087}, doi = {10.4230/LIPIcs.ICALP.2019.32}, annote = {Keywords: computational complexity, randomness, circuit lower bounds, Kolmogorov complexity} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Diptarka Chakraborty, Debarati Das, Michal Koucký, and Nitin Saurabh. Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chakraborty_et_al:LIPIcs.ESA.2018.12, author = {Chakraborty, Diptarka and Das, Debarati and Kouck\'{y}, Michal and Saurabh, Nitin}, title = {{Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {12:1--12:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah 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.2018.12}, URN = {urn:nbn:de:0030-drops-94750}, doi = {10.4230/LIPIcs.ESA.2018.12}, annote = {Keywords: Gray code, Space-optimal counter, Decision assignment tree, Cell probe model} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Debarati Das, Michal Koucký, and Michael Saks. Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 23:1-23:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{das_et_al:LIPIcs.STACS.2018.23, author = {Das, Debarati and Kouck\'{y}, Michal and Saks, Michael}, title = {{Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {23:1--23:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.23}, URN = {urn:nbn:de:0030-drops-85050}, doi = {10.4230/LIPIcs.STACS.2018.23}, annote = {Keywords: Lower bounds, Combinatorial algorithm, Boolean matrix multiplication} }
Feedback for Dagstuhl Publishing