LIPIcs, Volume 254
STACS 2023, March 7-9, 2023, Hamburg, Germany
Editors: Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté
LIPIcs, Volume 219
STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference)
Editors: Petra Berenbrink and Benjamin Monmege
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour, Dominik Kaaser, and Malin Rau. Dynamic Averaging Load Balancing on Arbitrary Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 18:1-18:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{berenbrink_et_al:LIPIcs.ICALP.2023.18, author = {Berenbrink, Petra and Hintze, Lukas and Hosseinpour, Hamed and Kaaser, Dominik and Rau, Malin}, title = {{Dynamic Averaging Load Balancing on Arbitrary Graphs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {18:1--18: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.18}, URN = {urn:nbn:de:0030-drops-180707}, doi = {10.4230/LIPIcs.ICALP.2023.18}, annote = {Keywords: Dynamic Load Balancing, Distributed Computing, Randomized Algorithms, Drift Analysis} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Petra Berenbrink, Mamadou Moustapha Kanté, Patricia Bouyer, and Anuj Dawar. LIPIcs, Volume 254, STACS 2023, Complete Volume. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 1-1026, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@Proceedings{berenbrink_et_al:LIPIcs.STACS.2023, title = {{LIPIcs, Volume 254, STACS 2023, Complete Volume}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {1--1026}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023}, URN = {urn:nbn:de:0030-drops-176515}, doi = {10.4230/LIPIcs.STACS.2023}, annote = {Keywords: LIPIcs, Volume 254, STACS 2023, Complete Volume} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté. Front Matter, Table of Contents, Preface, Conference Organization. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 0:i-0:xxii, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{berenbrink_et_al:LIPIcs.STACS.2023.0, author = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {0:i--0:xxii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.0}, URN = {urn:nbn:de:0030-drops-176525}, doi = {10.4230/LIPIcs.STACS.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Karoliina Lehtinen. A Brief History of History-Determinism (Invited Talk). In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 1:1-1:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{lehtinen:LIPIcs.STACS.2023.1, author = {Lehtinen, Karoliina}, title = {{A Brief History of History-Determinism}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {1:1--1:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.1}, URN = {urn:nbn:de:0030-drops-176535}, doi = {10.4230/LIPIcs.STACS.2023.1}, annote = {Keywords: History-determinism, nondeterminism, automata, good-for-games} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Eva Rotenberg. Amortised Analysis of Dynamic Data Structures (Invited Talk). In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 2:1-2:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{rotenberg:LIPIcs.STACS.2023.2, author = {Rotenberg, Eva}, title = {{Amortised Analysis of Dynamic Data Structures}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {2:1--2:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.2}, URN = {urn:nbn:de:0030-drops-176547}, doi = {10.4230/LIPIcs.STACS.2023.2}, annote = {Keywords: Amortised analysis, splaying, dynamic graphs, planarity testing} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Moshe Y. Vardi. Logical Algorithmics: From Theory to Practice (Invited Talk). In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, p. 3:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{vardi:LIPIcs.STACS.2023.3, author = {Vardi, Moshe Y.}, title = {{Logical Algorithmics: From Theory to Practice}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.3}, URN = {urn:nbn:de:0030-drops-176555}, doi = {10.4230/LIPIcs.STACS.2023.3}, annote = {Keywords: Logic, Algorithms} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Erhard Aichinger and Simon Grünbacher. The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 4:1-4:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{aichinger_et_al:LIPIcs.STACS.2023.4, author = {Aichinger, Erhard and Gr\"{u}nbacher, Simon}, title = {{The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {4:1--4:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.4}, URN = {urn:nbn:de:0030-drops-176560}, doi = {10.4230/LIPIcs.STACS.2023.4}, annote = {Keywords: quasi-identities, conditional identities, systems of equations} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Maxim Akhmedov and Maxim Babenko. Packing Odd Walks and Trails in Multiterminal Networks. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 5:1-5:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{akhmedov_et_al:LIPIcs.STACS.2023.5, author = {Akhmedov, Maxim and Babenko, Maxim}, title = {{Packing Odd Walks and Trails in Multiterminal Networks}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {5:1--5:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.5}, URN = {urn:nbn:de:0030-drops-176570}, doi = {10.4230/LIPIcs.STACS.2023.5}, annote = {Keywords: Odd path, signed and bidirected graph, multiflow, polynomial algorithm} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Cezar-Mihail Alexandru, Pavel Dvořák, Christian Konrad, and Kheeran K. Naidu. Improved Weighted Matching in the Sliding Window Model. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 6:1-6:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{alexandru_et_al:LIPIcs.STACS.2023.6, author = {Alexandru, Cezar-Mihail and Dvo\v{r}\'{a}k, Pavel and Konrad, Christian and Naidu, Kheeran K.}, title = {{Improved Weighted Matching in the Sliding Window Model}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {6:1--6:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.6}, URN = {urn:nbn:de:0030-drops-176585}, doi = {10.4230/LIPIcs.STACS.2023.6}, annote = {Keywords: Sliding window algorithms, Streaming algorithms, Maximum-weight matching} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Georgios Amanatidis and Pieter Kleer. Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 7:1-7:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{amanatidis_et_al:LIPIcs.STACS.2023.7, author = {Amanatidis, Georgios and Kleer, Pieter}, title = {{Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {7:1--7:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.7}, URN = {urn:nbn:de:0030-drops-176596}, doi = {10.4230/LIPIcs.STACS.2023.7}, annote = {Keywords: graph sampling, degree interval, degree sequence, Markov Chain Monte Carlo method, switch Markov chain} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Antoine Amarilli and Mikaël Monet. Enumerating Regular Languages with Bounded Delay. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 8:1-8:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{amarilli_et_al:LIPIcs.STACS.2023.8, author = {Amarilli, Antoine and Monet, Mika\"{e}l}, title = {{Enumerating Regular Languages with Bounded Delay}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {8:1--8:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.8}, URN = {urn:nbn:de:0030-drops-176609}, doi = {10.4230/LIPIcs.STACS.2023.8}, annote = {Keywords: Regular language, constant-delay enumeration, edit distance} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Pascal Baumann, Roland Meyer, and Georg Zetzsche. Regular Separability in Büchi VASS. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 9:1-9:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{baumann_et_al:LIPIcs.STACS.2023.9, author = {Baumann, Pascal and Meyer, Roland and Zetzsche, Georg}, title = {{Regular Separability in B\"{u}chi VASS}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {9:1--9:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.9}, URN = {urn:nbn:de:0030-drops-176617}, doi = {10.4230/LIPIcs.STACS.2023.9}, annote = {Keywords: Separability problem, Vector addition systems, Infinite words, Decidability} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Pierre Bergé, Édouard Bonnet, Hugues Déprés, and Rémi Watrigant. Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 10:1-10:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{berge_et_al:LIPIcs.STACS.2023.10, author = {Berg\'{e}, Pierre and Bonnet, \'{E}douard and D\'{e}pr\'{e}s, Hugues and Watrigant, R\'{e}mi}, title = {{Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.10}, URN = {urn:nbn:de:0030-drops-176629}, doi = {10.4230/LIPIcs.STACS.2023.10}, annote = {Keywords: Approximation algorithms, bounded twin-width} }
Feedback for Dagstuhl Publishing