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 319, 38th International Symposium on Distributed Computing (DISC 2024)
Philipp Czerner. Breaking Through the Ω(n)-Space Barrier: Population Protocols Decide Double-Exponential Thresholds. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{czerner:LIPIcs.DISC.2024.17, author = {Czerner, Philipp}, title = {{Breaking Through the \Omega(n)-Space Barrier: Population Protocols Decide Double-Exponential Thresholds}}, booktitle = {38th International Symposium on Distributed Computing (DISC 2024)}, pages = {17:1--17:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-352-2}, ISSN = {1868-8969}, year = {2024}, volume = {319}, editor = {Alistarh, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.17}, URN = {urn:nbn:de:0030-drops-212438}, doi = {10.4230/LIPIcs.DISC.2024.17}, annote = {Keywords: Distributed computing, population protocols, state complexity} }
Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)
Philipp Czerner, Vincent Fischer, and Roland Guttenberg. Brief Announcement: The Expressive Power of Uniform Population Protocols with Logarithmic Space. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 44:1-44:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{czerner_et_al:LIPIcs.DISC.2024.44, author = {Czerner, Philipp and Fischer, Vincent and Guttenberg, Roland}, title = {{Brief Announcement: The Expressive Power of Uniform Population Protocols with Logarithmic Space}}, booktitle = {38th International Symposium on Distributed Computing (DISC 2024)}, pages = {44:1--44:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-352-2}, ISSN = {1868-8969}, year = {2024}, volume = {319}, editor = {Alistarh, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.44}, URN = {urn:nbn:de:0030-drops-212726}, doi = {10.4230/LIPIcs.DISC.2024.44}, annote = {Keywords: Population Protocols, Uniform, Expressive Power} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Cezar-Mihail Alexandru and Christian Konrad. Interval Selection in Sliding Windows. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alexandru_et_al:LIPIcs.ESA.2024.8, author = {Alexandru, Cezar-Mihail and Konrad, Christian}, title = {{Interval Selection in Sliding Windows}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {8:1--8:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.8}, URN = {urn:nbn:de:0030-drops-210795}, doi = {10.4230/LIPIcs.ESA.2024.8}, annote = {Keywords: Sliding window algorithms, Streaming algorithms, Interval selection} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Jakub Tětek. Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{tetek:LIPIcs.APPROX/RANDOM.2024.73, author = {T\v{e}tek, Jakub}, title = {{Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {73:1--73:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.73}, URN = {urn:nbn:de:0030-drops-210660}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.73}, annote = {Keywords: Differential privacy, Randomized approximation algorithms} }
Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)
Sebastian Schmidt, Santeri Toivonen, Paul Medvedev, and Alexandru I. Tomescu. Applying the Safe-And-Complete Framework to Practical Genome Assembly. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{schmidt_et_al:LIPIcs.WABI.2024.8, author = {Schmidt, Sebastian and Toivonen, Santeri and Medvedev, Paul and Tomescu, Alexandru I.}, title = {{Applying the Safe-And-Complete Framework to Practical Genome Assembly}}, booktitle = {24th International Workshop on Algorithms in Bioinformatics (WABI 2024)}, pages = {8:1--8:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-340-9}, ISSN = {1868-8969}, year = {2024}, volume = {312}, editor = {Pissis, Solon P. and Sung, Wing-Kin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.8}, URN = {urn:nbn:de:0030-drops-206520}, doi = {10.4230/LIPIcs.WABI.2024.8}, annote = {Keywords: Genome assembly, Omnitigs, Safe-and-complete framework, graph algorithm, HiFi sequencing data, Assembly evaluation} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Satyadev Nandakumar, Subin Pulari, and Akhil S. Point-To-Set Principle and Constructive Dimension Faithfulness. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{nandakumar_et_al:LIPIcs.MFCS.2024.76, author = {Nandakumar, Satyadev and Pulari, Subin and S, Akhil}, title = {{Point-To-Set Principle and Constructive Dimension Faithfulness}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {76:1--76:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.76}, URN = {urn:nbn:de:0030-drops-206321}, doi = {10.4230/LIPIcs.MFCS.2024.76}, annote = {Keywords: Kolmogorov complexity, Constructive dimension, Faithfulness, Point to set principle, Continued fraction dimension, Cantor series expansion} }
Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)
Friedrich Slivovsky. Strategy Extraction by Interpolation. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{slivovsky:LIPIcs.SAT.2024.28, author = {Slivovsky, Friedrich}, title = {{Strategy Extraction by Interpolation}}, booktitle = {27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)}, pages = {28:1--28:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-334-8}, ISSN = {1868-8969}, year = {2024}, volume = {305}, editor = {Chakraborty, Supratik and Jiang, Jie-Hong Roland}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.28}, URN = {urn:nbn:de:0030-drops-205509}, doi = {10.4230/LIPIcs.SAT.2024.28}, annote = {Keywords: QBF, Expansion, Strategy Extraction, Interpolation} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Philip Mayer and Petra Mutzel. Engineering A* Search for the Flip Distance of Plane Triangulations. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mayer_et_al:LIPIcs.SEA.2024.23, author = {Mayer, Philip and Mutzel, Petra}, title = {{Engineering A* Search for the Flip Distance of Plane Triangulations}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {23:1--23:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.23}, URN = {urn:nbn:de:0030-drops-203887}, doi = {10.4230/LIPIcs.SEA.2024.23}, annote = {Keywords: Computational Geometry, Triangulations, Flip Distance, A-star Search, Integer Linear Programming} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Holger Dell, John Lapinskas, and Kitty Meeks. Nearly Optimal Independence Oracle Algorithms for Edge Estimation in Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dell_et_al:LIPIcs.ICALP.2024.54, author = {Dell, Holger and Lapinskas, John and Meeks, Kitty}, title = {{Nearly Optimal Independence Oracle Algorithms for Edge Estimation in Hypergraphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {54:1--54:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.54}, URN = {urn:nbn:de:0030-drops-201977}, doi = {10.4230/LIPIcs.ICALP.2024.54}, annote = {Keywords: Graph oracles, Fine-grained complexity, Approximate counting, Hypergraphs} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Narek Bojikian and Stefan Kratsch. A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bojikian_et_al:LIPIcs.ICALP.2024.29, author = {Bojikian, Narek and Kratsch, Stefan}, title = {{A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {29:1--29:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.29}, URN = {urn:nbn:de:0030-drops-201728}, doi = {10.4230/LIPIcs.ICALP.2024.29}, annote = {Keywords: Parameterized complexity, Steiner tree, clique-width} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, and Paweł Rzążewski. Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 77:1-77:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{groenland_et_al:LIPIcs.ICALP.2024.77, author = {Groenland, Carla and Mannens, Isja and Nederlof, Jesper and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {77:1--77:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.77}, URN = {urn:nbn:de:0030-drops-202208}, doi = {10.4230/LIPIcs.ICALP.2024.77}, annote = {Keywords: graph homomorphism, cutwidth, asymptotic matrix parameters} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Martin Grohe and Daniel Neuen. Isomorphism for Tournaments of Small Twin Width. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 78:1-78:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{grohe_et_al:LIPIcs.ICALP.2024.78, author = {Grohe, Martin and Neuen, Daniel}, title = {{Isomorphism for Tournaments of Small Twin Width}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {78:1--78:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.78}, URN = {urn:nbn:de:0030-drops-202216}, doi = {10.4230/LIPIcs.ICALP.2024.78}, annote = {Keywords: tournament isomorphism, twin width, fixed-parameter tractability, Weisfeiler-Leman algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 88:1-88:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{inamdar_et_al:LIPIcs.ICALP.2024.88, author = {Inamdar, Tanmay and Jain, Pallavi and Lokshtanov, Daniel and Sahu, Abhishek and Saurabh, Saket and Upasana, Anannya}, title = {{Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {88:1--88:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.88}, URN = {urn:nbn:de:0030-drops-202318}, doi = {10.4230/LIPIcs.ICALP.2024.88}, annote = {Keywords: Partial Vertex Cover, Max SAT, FPT Approximation, Matroids} }
Feedback for Dagstuhl Publishing