Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, and Pengxiang Wang. Robustness for Space-Bounded Statistical Zero Knowledge. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 56:1-56:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{allender_et_al:LIPIcs.APPROX/RANDOM.2023.56, author = {Allender, Eric and Gray, Jacob and Mutreja, Saachi and Tirumala, Harsha and Wang, Pengxiang}, title = {{Robustness for Space-Bounded Statistical Zero Knowledge}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {56:1--56:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.56}, URN = {urn:nbn:de:0030-drops-188815}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.56}, annote = {Keywords: Interactive Proofs} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Ruiwen Dong. The Identity Problem in ℤ ≀ ℤ Is Decidable. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 124:1-124:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dong:LIPIcs.ICALP.2023.124, author = {Dong, Ruiwen}, title = {{The Identity Problem in \mathbb{Z} ≀ \mathbb{Z} Is Decidable}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {124:1--124:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.124}, URN = {urn:nbn:de:0030-drops-181768}, doi = {10.4230/LIPIcs.ICALP.2023.124}, annote = {Keywords: wreath product, algorithmic group theory, identity problem, polynomial semiring, positive coefficients} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Markus Lohrey and Andreas Rosowski. On the Complexity of Diameter and Related Problems in Permutation Groups. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 134:1-134:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lohrey_et_al:LIPIcs.ICALP.2023.134, author = {Lohrey, Markus and Rosowski, Andreas}, title = {{On the Complexity of Diameter and Related Problems in Permutation Groups}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {134:1--134:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.134}, URN = {urn:nbn:de:0030-drops-181864}, doi = {10.4230/LIPIcs.ICALP.2023.134}, annote = {Keywords: algorithms for finite groups, diameter of permutation groups, rational subsets in groups} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Moses Ganardi, Louis Jachiet, Markus Lohrey, and Thomas Schwentick. Low-Latency Sliding Window Algorithms for Formal Languages. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 38:1-38:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ganardi_et_al:LIPIcs.FSTTCS.2022.38, author = {Ganardi, Moses and Jachiet, Louis and Lohrey, Markus and Schwentick, Thomas}, title = {{Low-Latency Sliding Window Algorithms for Formal Languages}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {38:1--38:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.38}, URN = {urn:nbn:de:0030-drops-174301}, doi = {10.4230/LIPIcs.FSTTCS.2022.38}, annote = {Keywords: Streaming algorithms, regular languages, context-free languages} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Markus Lohrey, Andreas Rosowski, and Georg Zetzsche. Membership Problems in Finite Groups. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lohrey_et_al:LIPIcs.MFCS.2022.71, author = {Lohrey, Markus and Rosowski, Andreas and Zetzsche, Georg}, title = {{Membership Problems in Finite Groups}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {71:1--71:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.71}, URN = {urn:nbn:de:0030-drops-168694}, doi = {10.4230/LIPIcs.MFCS.2022.71}, annote = {Keywords: algorithms for finite groups, intersection non-emptiness problems, knapsack problems in groups} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Markus Lohrey and Lukas Lück. Streaming Word Problems. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lohrey_et_al:LIPIcs.MFCS.2022.72, author = {Lohrey, Markus and L\"{u}ck, Lukas}, title = {{Streaming Word Problems}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {72:1--72:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.72}, URN = {urn:nbn:de:0030-drops-168707}, doi = {10.4230/LIPIcs.MFCS.2022.72}, annote = {Keywords: word problems for groups, streaming algorithms} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
J. Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner, and Sebastian Wild. Hypersuccinct Trees - New Universal Tree Source Codes for Optimal Compressed Tree Data Structures and Range Minima. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 70:1-70:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{munro_et_al:LIPIcs.ESA.2021.70, author = {Munro, J. Ian and Nicholson, Patrick K. and Benkner, Louisa Seelbach and Wild, Sebastian}, title = {{Hypersuccinct Trees - New Universal Tree Source Codes for Optimal Compressed Tree Data Structures and Range Minima}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {70:1--70:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.70}, URN = {urn:nbn:de:0030-drops-146512}, doi = {10.4230/LIPIcs.ESA.2021.70}, annote = {Keywords: analysis of algorithms, universal source code, compressed trees, succinct data structure, succinct trees, tree covering, random binary search trees, range-minimum queries} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Markus Lohrey. Subgroup Membership in GL(2,Z). In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{lohrey:LIPIcs.STACS.2021.51, author = {Lohrey, Markus}, title = {{Subgroup Membership in GL(2,Z)}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {51:1--51: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.51}, URN = {urn:nbn:de:0030-drops-136961}, doi = {10.4230/LIPIcs.STACS.2021.51}, annote = {Keywords: free groups, virtually free groups, subgroup membership, matrix groups} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Markus Lohrey and Georg Zetzsche. Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 67:1-67:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{lohrey_et_al:LIPIcs.MFCS.2020.67, author = {Lohrey, Markus and Zetzsche, Georg}, title = {{Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {67:1--67:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.67}, URN = {urn:nbn:de:0030-drops-127364}, doi = {10.4230/LIPIcs.MFCS.2020.67}, annote = {Keywords: computational group theory, matrix problems, Baumslag-Solitar groups} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Weiß. Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 29:1-29:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bartholdi_et_al:LIPIcs.CCC.2020.29, author = {Bartholdi, Laurent and Figelius, Michael and Lohrey, Markus and Wei{\ss}, Armin}, title = {{Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {29:1--29:29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.29}, URN = {urn:nbn:de:0030-drops-125814}, doi = {10.4230/LIPIcs.CCC.2020.29}, annote = {Keywords: NC^1-hardness, word problem, G-programs, straight-line programs, non-solvable groups, self-similar groups, Thompson’s groups, Grigorchuk’s group} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Michael Figelius, Moses Ganardi, Markus Lohrey, and Georg Zetzsche. The Complexity of Knapsack Problems in Wreath Products. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 126:1-126:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{figelius_et_al:LIPIcs.ICALP.2020.126, author = {Figelius, Michael and Ganardi, Moses and Lohrey, Markus and Zetzsche, Georg}, title = {{The Complexity of Knapsack Problems in Wreath Products}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {126:1--126:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.126}, URN = {urn:nbn:de:0030-drops-125339}, doi = {10.4230/LIPIcs.ICALP.2020.126}, annote = {Keywords: algorithmic group theory, knapsack, wreath product} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding Window Property Testing for Regular Languages. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ganardi_et_al:LIPIcs.ISAAC.2019.6, author = {Ganardi, Moses and Hucke, Danny and Lohrey, Markus and Starikovskaya, Tatiana}, title = {{Sliding Window Property Testing for Regular Languages}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.6}, URN = {urn:nbn:de:0030-drops-115023}, doi = {10.4230/LIPIcs.ISAAC.2019.6}, annote = {Keywords: Streaming algorithms, approximation algorithms, regular languages} }
Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)
Volker Diekert, Olga Kharlampovich, Markus Lohrey, and Alexei Myasnikov. Algorithmic Problems in Group Theory (Dagstuhl Seminar 19131). In Dagstuhl Reports, Volume 9, Issue 3, pp. 83-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{diekert_et_al:DagRep.9.3.83, author = {Diekert, Volker and Kharlampovich, Olga and Lohrey, Markus and Myasnikov, Alexei}, title = {{Algorithmic Problems in Group Theory (Dagstuhl Seminar 19131)}}, pages = {83--110}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {3}, editor = {Diekert, Volker and Kharlampovich, Olga and Lohrey, Markus and Myasnikov, Alexei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.3.83}, URN = {urn:nbn:de:0030-drops-112939}, doi = {10.4230/DagRep.9.3.83}, annote = {Keywords: algorithmic group theory; generic-case complexity; circuit complexity; diophantine theories} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Markus Lohrey and Armin Weiß. The Power Word Problem. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lohrey_et_al:LIPIcs.MFCS.2019.43, author = {Lohrey, Markus and Wei{\ss}, Armin}, title = {{The Power Word Problem}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {43:1--43:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.43}, URN = {urn:nbn:de:0030-drops-109871}, doi = {10.4230/LIPIcs.MFCS.2019.43}, annote = {Keywords: word problem, compressed word problem, free groups} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Derek Holt, Markus Lohrey, and Saul Schleimer. Compressed Decision Problems in Hyperbolic Groups. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{holt_et_al:LIPIcs.STACS.2019.37, author = {Holt, Derek and Lohrey, Markus and Schleimer, Saul}, title = {{Compressed Decision Problems in Hyperbolic Groups}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {37:1--37:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.37}, URN = {urn:nbn:de:0030-drops-102766}, doi = {10.4230/LIPIcs.STACS.2019.37}, annote = {Keywords: hyperbolic groups, algorithms for compressed words, circuit evaluation problems} }
Feedback for Dagstuhl Publishing