LIPIcs, Volume 219
STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference)
Editors: Petra Berenbrink and Benjamin Monmege
LIPIcs, Volume 187
STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference)
Editors: Markus Bläser and Benjamin Monmege
Published in: LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022)
Benjamin Monmege, Julie Parreaux, and Pierre-Alain Reynier. Decidability of One-Clock Weighted Timed Games with Arbitrary Weights. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{monmege_et_al:LIPIcs.CONCUR.2022.15, author = {Monmege, Benjamin and Parreaux, Julie and Reynier, Pierre-Alain}, title = {{Decidability of One-Clock Weighted Timed Games with Arbitrary Weights}}, booktitle = {33rd International Conference on Concurrency Theory (CONCUR 2022)}, pages = {15:1--15:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-246-4}, ISSN = {1868-8969}, year = {2022}, volume = {243}, editor = {Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.15}, URN = {urn:nbn:de:0030-drops-170786}, doi = {10.4230/LIPIcs.CONCUR.2022.15}, annote = {Keywords: Weighted timed games, Algorithmic game theory, Timed automata} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 1-1044, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Proceedings{berenbrink_et_al:LIPIcs.STACS.2022, title = {{LIPIcs, Volume 219, STACS 2022, Complete Volume}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {1--1044}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022}, URN = {urn:nbn:de:0030-drops-158098}, doi = {10.4230/LIPIcs.STACS.2022}, annote = {Keywords: LIPIcs, Volume 219, STACS 2022, Complete Volume} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{berenbrink_et_al:LIPIcs.STACS.2022.0, author = {Berenbrink, Petra and Monmege, Benjamin}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.0}, URN = {urn:nbn:de:0030-drops-158101}, doi = {10.4230/LIPIcs.STACS.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Marie Albenque. Local Limit of Random Discrete Surface with (Or Without!) a Statistical Physics Model (Invited Talk). In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{albenque:LIPIcs.STACS.2022.1, author = {Albenque, Marie}, title = {{Local Limit of Random Discrete Surface with (Or Without!) a Statistical Physics Model}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {1:1--1:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.1}, URN = {urn:nbn:de:0030-drops-158118}, doi = {10.4230/LIPIcs.STACS.2022.1}, annote = {Keywords: Random graphs, triangulations, Benjamini-Schramm convergence, Ising model} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Maria-Florina Balcan. Generalization Guarantees for Data-Driven Mechanism Design (Invited Talk). In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{balcan:LIPIcs.STACS.2022.2, author = {Balcan, Maria-Florina}, title = {{Generalization Guarantees for Data-Driven Mechanism Design}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.2}, URN = {urn:nbn:de:0030-drops-158127}, doi = {10.4230/LIPIcs.STACS.2022.2}, annote = {Keywords: mechanism configuration, algorithm configuration, machine learning, generalization guarantees} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Fabian Kuhn. Deterministic Distributed Symmetry Breaking at the Example of Distributed Graph Coloring (Invited Talk). In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kuhn:LIPIcs.STACS.2022.3, author = {Kuhn, Fabian}, title = {{Deterministic Distributed Symmetry Breaking at the Example of Distributed Graph Coloring}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.3}, URN = {urn:nbn:de:0030-drops-158131}, doi = {10.4230/LIPIcs.STACS.2022.3}, annote = {Keywords: distributed graph algorithms, derandomization, distributed coloring} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Mapping Networks via Parallel kth-Hop Traceroute Queries. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{afshar_et_al:LIPIcs.STACS.2022.4, author = {Afshar, Ramtin and Goodrich, Michael T. and Matias, Pedro and Osegueda, Martha C.}, title = {{Mapping Networks via Parallel kth-Hop Traceroute Queries}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {4:1--4:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.4}, URN = {urn:nbn:de:0030-drops-158142}, doi = {10.4230/LIPIcs.STACS.2022.4}, annote = {Keywords: Network mapping, graph algorithms, parallel algorithms, distributed computing, query complexity, kth-hop queries} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
S. Akshay, Hugo Bazille, Blaise Genest, and Mihir Vahanwala. On Robustness for the Skolem and Positivity Problems. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{akshay_et_al:LIPIcs.STACS.2022.5, author = {Akshay, S. and Bazille, Hugo and Genest, Blaise and Vahanwala, Mihir}, title = {{On Robustness for the Skolem and Positivity Problems}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.5}, URN = {urn:nbn:de:0030-drops-158156}, doi = {10.4230/LIPIcs.STACS.2022.5}, annote = {Keywords: Skolem problem, verification, dynamical systems, robustness} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Yacine Al-Najjar, Walid Ben-Ameur, and Jérémie Leguay. Approximability of Robust Network Design: The Directed Case. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{alnajjar_et_al:LIPIcs.STACS.2022.6, author = {Al-Najjar, Yacine and Ben-Ameur, Walid and Leguay, J\'{e}r\'{e}mie}, title = {{Approximability of Robust Network Design: The Directed Case}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {6:1--6:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.6}, URN = {urn:nbn:de:0030-drops-158165}, doi = {10.4230/LIPIcs.STACS.2022.6}, annote = {Keywords: Robust Optimization, Network Design, Approximation, Inapproximability, Competitive Ratio of Oblivious Routing} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Pascal Baumann, Moses Ganardi, Ramanathan S. Thinniyam, and Georg Zetzsche. Existential Definability over the Subword Ordering. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{baumann_et_al:LIPIcs.STACS.2022.7, author = {Baumann, Pascal and Ganardi, Moses and Thinniyam, Ramanathan S. and Zetzsche, Georg}, title = {{Existential Definability over the Subword Ordering}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {7:1--7:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.7}, URN = {urn:nbn:de:0030-drops-158178}, doi = {10.4230/LIPIcs.STACS.2022.7}, annote = {Keywords: subword, subsequence, definability, expressiveness, first order logic, existential fragment, quantifier alternation} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski. Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bazhenov_et_al:LIPIcs.STACS.2022.8, author = {Bazhenov, Nikolay and Kaloci\'{n}ski, Dariusz and Wroc{\l}awski, Micha{\l}}, title = {{Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.8}, URN = {urn:nbn:de:0030-drops-158185}, doi = {10.4230/LIPIcs.STACS.2022.8}, annote = {Keywords: Computable Structure Theory, Degree Spectra, \omega-Type Order, c.e. Degrees, d.c.e. Degrees, \Delta₂ Degrees, Learnability} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Pierre Bergé, Guillaume Ducoffe, and Michel Habib. Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{berge_et_al:LIPIcs.STACS.2022.9, author = {Berg\'{e}, Pierre and Ducoffe, Guillaume and Habib, Michel}, title = {{Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {9:1--9:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.9}, URN = {urn:nbn:de:0030-drops-158192}, doi = {10.4230/LIPIcs.STACS.2022.9}, annote = {Keywords: Diameter, Eccentricities, Metric graph theory, Median graphs, Hypercubes} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Faster Counting and Sampling Algorithms Using Colorful Decision Oracle. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bhattacharya_et_al:LIPIcs.STACS.2022.10, author = {Bhattacharya, Anup and Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath}, title = {{Faster Counting and Sampling Algorithms Using Colorful Decision Oracle}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.10}, URN = {urn:nbn:de:0030-drops-158205}, doi = {10.4230/LIPIcs.STACS.2022.10}, annote = {Keywords: Query Complexity, Subset Query, Hyperedge Estimation, and Colorful Independent Set oracle} }
Feedback for Dagstuhl Publishing