Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Sungjin Im, Benjamin Moseley, Hung Ngo, and Kirk Pruhs. On the Convergence Rate of Linear Datalog ^∘ over Stable Semirings. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{im_et_al:LIPIcs.ICDT.2024.11, author = {Im, Sungjin and Moseley, Benjamin and Ngo, Hung and Pruhs, Kirk}, title = {{On the Convergence Rate of Linear Datalog ^∘ over Stable Semirings}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {11:1--11:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.11}, URN = {urn:nbn:de:0030-drops-197939}, doi = {10.4230/LIPIcs.ICDT.2024.11}, annote = {Keywords: Datalog, convergence rate, semiring} }
Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Antoine Amarilli, Pierre Bourhis, Florent Capelli, and Mikaël Monet. Ranked Enumeration for MSO on Trees via Knowledge Compilation. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{amarilli_et_al:LIPIcs.ICDT.2024.25, author = {Amarilli, Antoine and Bourhis, Pierre and Capelli, Florent and Monet, Mika\"{e}l}, title = {{Ranked Enumeration for MSO on Trees via Knowledge Compilation}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {25:1--25:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.25}, URN = {urn:nbn:de:0030-drops-198079}, doi = {10.4230/LIPIcs.ICDT.2024.25}, annote = {Keywords: Enumeration, knowledge compilation, monadic second-order logic} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Piotr Kawałek, Michael Kompatscher, and Jacek Krzaczkowski. Circuit Equivalence in 2-Nilpotent Algebras. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 45:1-45:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kawalek_et_al:LIPIcs.STACS.2024.45, author = {Kawa{\l}ek, Piotr and Kompatscher, Michael and Krzaczkowski, Jacek}, title = {{Circuit Equivalence in 2-Nilpotent Algebras}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {45:1--45:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.45}, URN = {urn:nbn:de:0030-drops-197554}, doi = {10.4230/LIPIcs.STACS.2024.45}, annote = {Keywords: circuit equivalence, identity checking, nilpotent algebra} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Michael Chen, A. Pavan, and N. V. Vinodchandran. Brief Announcement: Relations Between Space-Bounded and Adaptive Massively Parallel Computations. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 37:1-37:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.DISC.2023.37, author = {Chen, Michael and Pavan, A. and Vinodchandran, N. V.}, title = {{Brief Announcement: Relations Between Space-Bounded and Adaptive Massively Parallel Computations}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {37:1--37:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.37}, URN = {urn:nbn:de:0030-drops-191634}, doi = {10.4230/LIPIcs.DISC.2023.37}, annote = {Keywords: Massively Parallel Computation, AMPC, Complexity Classes, LogSpace, NL, PSPACE} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Michaël Cadilhac, Arka Ghosh, Guillermo A. Pérez, and Ritam Raha. Parikh One-Counter Automata. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cadilhac_et_al:LIPIcs.MFCS.2023.30, author = {Cadilhac, Micha\"{e}l and Ghosh, Arka and P\'{e}rez, Guillermo A. and Raha, Ritam}, title = {{Parikh One-Counter Automata}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {30:1--30:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.30}, URN = {urn:nbn:de:0030-drops-185645}, doi = {10.4230/LIPIcs.MFCS.2023.30}, annote = {Keywords: Parikh automata, Context-free languages, One-counter automata} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal Algorithms for Learning Quantum Phase States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arunachalam_et_al:LIPIcs.TQC.2023.3, author = {Arunachalam, Srinivasan and Bravyi, Sergey and Dutt, Arkopal and Yoder, Theodore J.}, title = {{Optimal Algorithms for Learning Quantum Phase States}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {3:1--3:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-283-9}, ISSN = {1868-8969}, year = {2023}, volume = {266}, editor = {Fawzi, Omar and Walter, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.3}, URN = {urn:nbn:de:0030-drops-183139}, doi = {10.4230/LIPIcs.TQC.2023.3}, annote = {Keywords: Tomography, binary phase states, generalized phase states, IQP circuits} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Oswin Aichholzer, Man-Kwun Chiu, Hung P. Hoang, Michael Hoffmann, Jan Kynčl, Yannic Maus, Birgit Vogtenhuber, and Alexandra Weinberger. Drawings of Complete Multipartite Graphs up to Triangle Flips. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2023.6, author = {Aichholzer, Oswin and Chiu, Man-Kwun and Hoang, Hung P. and Hoffmann, Michael and Kyn\v{c}l, Jan and Maus, Yannic and Vogtenhuber, Birgit and Weinberger, Alexandra}, title = {{Drawings of Complete Multipartite Graphs up to Triangle Flips}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {6:1--6:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.6}, URN = {urn:nbn:de:0030-drops-178563}, doi = {10.4230/LIPIcs.SoCG.2023.6}, annote = {Keywords: Simple drawings, simple topological graphs, complete graphs, multipartite graphs, k-partite graphs, bipartite graphs, Gioan’s Theorem, triangle flips, Reidemeister moves} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Mickaël Buchet, Bianca B. Dornelas, and Michael Kerber. Sparse Higher Order Čech Filtrations. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{buchet_et_al:LIPIcs.SoCG.2023.20, author = {Buchet, Micka\"{e}l and B. Dornelas, Bianca and Kerber, Michael}, title = {{Sparse Higher Order \v{C}ech Filtrations}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {20:1--20:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.20}, URN = {urn:nbn:de:0030-drops-178709}, doi = {10.4230/LIPIcs.SoCG.2023.20}, annote = {Keywords: Sparsification, k-fold cover, Higher order \v{C}ech complexes} }
Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)
Michael Ballantyne and Matthias Felleisen. Injecting Language Workbench Technology into Mainstream Languages. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ballantyne_et_al:OASIcs.EVCS.2023.3, author = {Ballantyne, Michael and Felleisen, Matthias}, title = {{Injecting Language Workbench Technology into Mainstream Languages}}, booktitle = {Eelco Visser Commemorative Symposium (EVCS 2023)}, pages = {3:1--3:11}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-267-9}, ISSN = {2190-6807}, year = {2023}, volume = {109}, editor = {L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.3}, URN = {urn:nbn:de:0030-drops-177737}, doi = {10.4230/OASIcs.EVCS.2023.3}, annote = {Keywords: Language workbenches, macro systems, language adoption} }
Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)
Michael Greenberg. Reasoning About Paths in the Interface Graph. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 11:1-11:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{greenberg:OASIcs.EVCS.2023.11, author = {Greenberg, Michael}, title = {{Reasoning About Paths in the Interface Graph}}, booktitle = {Eelco Visser Commemorative Symposium (EVCS 2023)}, pages = {11:1--11:11}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-267-9}, ISSN = {2190-6807}, year = {2023}, volume = {109}, editor = {L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.11}, URN = {urn:nbn:de:0030-drops-177812}, doi = {10.4230/OASIcs.EVCS.2023.11}, annote = {Keywords: interfaces, components, lambda calculus, dynamic analysis} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Michael Saks and Rahul Santhanam. On Randomized Reductions to the Random Strings. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 29:1-29:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{saks_et_al:LIPIcs.CCC.2022.29, author = {Saks, Michael and Santhanam, Rahul}, title = {{On Randomized Reductions to the Random Strings}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {29:1--29:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.29}, URN = {urn:nbn:de:0030-drops-165912}, doi = {10.4230/LIPIcs.CCC.2022.29}, annote = {Keywords: Kolmogorov complexity, randomized reductions} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amit Deshpande and Rameshwar Pratap. One-Pass Additive-Error Subset Selection for 𝓁_p Subspace Approximation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{deshpande_et_al:LIPIcs.ICALP.2022.51, author = {Deshpande, Amit and Pratap, Rameshwar}, title = {{One-Pass Additive-Error Subset Selection for 𝓁\underlinep Subspace Approximation}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {51:1--51:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.51}, URN = {urn:nbn:de:0030-drops-163924}, doi = {10.4230/LIPIcs.ICALP.2022.51}, annote = {Keywords: Subspace approximation, streaming algorithms, low-rank approximation, adaptive sampling, volume sampling, subset selection} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Jakub Łącki and Yasamin Nazari. Near-Optimal Decremental Hopsets with Applications. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 86:1-86:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lacki_et_al:LIPIcs.ICALP.2022.86, author = {{\L}\k{a}cki, Jakub and Nazari, Yasamin}, title = {{Near-Optimal Decremental Hopsets with Applications}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {86:1--86:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.86}, URN = {urn:nbn:de:0030-drops-164277}, doi = {10.4230/LIPIcs.ICALP.2022.86}, annote = {Keywords: Dynamic Algorithms, Data Structures, Shortest Paths, Hopsets} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, and Hao-Tsung Yang. On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{afshani_et_al:LIPIcs.SoCG.2022.2, author = {Afshani, Peyman and de Berg, Mark and Buchin, Kevin and Gao, Jie and L\"{o}ffler, Maarten and Nayyeri, Amir and Raichel, Benjamin and Sarkar, Rik and Wang, Haotian and Yang, Hao-Tsung}, title = {{On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {2:1--2:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.2}, URN = {urn:nbn:de:0030-drops-160109}, doi = {10.4230/LIPIcs.SoCG.2022.2}, annote = {Keywords: Approximation, Motion Planning, Scheduling} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Karl Bringmann, Sándor Kisfaludi‑Bak, Marvin Künnemann, Dániel Marx, and André Nusser. Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bringmann_et_al:LIPIcs.SoCG.2022.20, author = {Bringmann, Karl and Kisfaludi‑Bak, S\'{a}ndor and K\"{u}nnemann, Marvin and Marx, D\'{a}niel and Nusser, Andr\'{e}}, title = {{Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {20:1--20:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.20}, URN = {urn:nbn:de:0030-drops-160287}, doi = {10.4230/LIPIcs.SoCG.2022.20}, annote = {Keywords: Dynamic Time Warping, Sequence Similarity Measures} }
Feedback for Dagstuhl Publishing