Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7, author = {Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik}, title = {{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.7}, URN = {urn:nbn:de:0030-drops-204035}, doi = {10.4230/LIPIcs.CCC.2024.7}, annote = {Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Josh Alman and Yunfeng Guan. Finer-Grained Hardness of Kernel Density Estimation. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 35:1-35:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alman_et_al:LIPIcs.CCC.2024.35, author = {Alman, Josh and Guan, Yunfeng}, title = {{Finer-Grained Hardness of Kernel Density Estimation}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {35:1--35:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.35}, URN = {urn:nbn:de:0030-drops-204311}, doi = {10.4230/LIPIcs.CCC.2024.35}, annote = {Keywords: Kernel Density Estimation, Fine-Grained Complexity, Schur Polynomials} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Daniel Hambly, Rhyd Lewis, and Padraig Corcoran. Determining Fixed-Length Paths in Directed and Undirected Edge-Weighted Graphs. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 15:1-15:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hambly_et_al:LIPIcs.SEA.2024.15, author = {Hambly, Daniel and Lewis, Rhyd and Corcoran, Padraig}, title = {{Determining Fixed-Length Paths in Directed and Undirected Edge-Weighted Graphs}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {15:1--15:11}, 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.15}, URN = {urn:nbn:de:0030-drops-203805}, doi = {10.4230/LIPIcs.SEA.2024.15}, annote = {Keywords: Graphs, paths, backtracking, integer programming, Yen’s algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Panagiotis Charalampopoulos, Paweł Gawrychowski, and Samah Ghazawi. Optimal Bounds for Distinct Quartics. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{charalampopoulos_et_al:LIPIcs.ICALP.2024.39, author = {Charalampopoulos, Panagiotis and Gawrychowski, Pawe{\l} and Ghazawi, Samah}, title = {{Optimal Bounds for Distinct Quartics}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {39:1--39: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.39}, URN = {urn:nbn:de:0030-drops-201823}, doi = {10.4230/LIPIcs.ICALP.2024.39}, annote = {Keywords: 2D strings, quartics, repetitions, periodicity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yu Chen, Michael Kapralov, Mikhail Makarov, and Davide Mazzali. On the Streaming Complexity of Expander Decomposition. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.46, author = {Chen, Yu and Kapralov, Michael and Makarov, Mikhail and Mazzali, Davide}, title = {{On the Streaming Complexity of Expander Decomposition}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {46:1--46: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.46}, URN = {urn:nbn:de:0030-drops-201890}, doi = {10.4230/LIPIcs.ICALP.2024.46}, annote = {Keywords: Graph Sketching, Dynamic Streaming, Expander Decomposition} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Ilan Doron-Arad and Joseph (Seffi) Naor. Non-Linear Paging. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{doronarad_et_al:LIPIcs.ICALP.2024.57, author = {Doron-Arad, Ilan and Naor, Joseph (Seffi)}, title = {{Non-Linear Paging}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {57:1--57:19}, 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.57}, URN = {urn:nbn:de:0030-drops-202000}, doi = {10.4230/LIPIcs.ICALP.2024.57}, annote = {Keywords: paging, competitive analysis, non-linear paging, submodular and supermodular functions} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sylvain Schmitz and Lia Schütze. On the Length of Strongly Monotone Descending Chains over ℕ^d. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 153:1-153:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{schmitz_et_al:LIPIcs.ICALP.2024.153, author = {Schmitz, Sylvain and Sch\"{u}tze, Lia}, title = {{On the Length of Strongly Monotone Descending Chains over \mathbb{N}^d}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {153:1--153:19}, 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.153}, URN = {urn:nbn:de:0030-drops-202964}, doi = {10.4230/LIPIcs.ICALP.2024.153}, annote = {Keywords: Vector addition system, coverability, well-quasi-order, order ideal, affine net} }
Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1
Andreas Harth, Tobias Käfer, Anisa Rula, Jean-Paul Calbimonte, Eduard Kamburjan, and Martin Giese. Towards Representing Processes and Reasoning with Process Descriptions on the Web. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 1:1-1:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{harth_et_al:TGDK.2.1.1, author = {Harth, Andreas and K\"{a}fer, Tobias and Rula, Anisa and Calbimonte, Jean-Paul and Kamburjan, Eduard and Giese, Martin}, title = {{Towards Representing Processes and Reasoning with Process Descriptions on the Web}}, journal = {Transactions on Graph Data and Knowledge}, pages = {1:1--1:32}, ISSN = {2942-7517}, year = {2024}, volume = {2}, number = {1}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.1}, URN = {urn:nbn:de:0030-drops-198583}, doi = {10.4230/TGDK.2.1.1}, annote = {Keywords: Process modelling, Process ontology, Temporal logic, Web services} }
Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1
Bradley P. Allen and Filip Ilievski. Standardizing Knowledge Engineering Practices with a Reference Architecture. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{allen_et_al:TGDK.2.1.5, author = {Allen, Bradley P. and Ilievski, Filip}, title = {{Standardizing Knowledge Engineering Practices with a Reference Architecture}}, journal = {Transactions on Graph Data and Knowledge}, pages = {5:1--5:23}, ISSN = {2942-7517}, year = {2024}, volume = {2}, number = {1}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.5}, URN = {urn:nbn:de:0030-drops-198623}, doi = {10.4230/TGDK.2.1.5}, annote = {Keywords: knowledge engineering, knowledge graphs, quality attributes, software architectures, sociotechnical systems} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Ting-Yu Kuo, Yu-Han Chen, Andrea Frosini, Sun-Yuan Hsieh, Shi-Chun Tsai, and Mong-Jen Kao. On Min-Max Graph Balancing with Strict Negative Correlation Constraints. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kuo_et_al:LIPIcs.ISAAC.2023.50, author = {Kuo, Ting-Yu and Chen, Yu-Han and Frosini, Andrea and Hsieh, Sun-Yuan and Tsai, Shi-Chun and Kao, Mong-Jen}, title = {{On Min-Max Graph Balancing with Strict Negative Correlation Constraints}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {50:1--50:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.50}, URN = {urn:nbn:de:0030-drops-193524}, doi = {10.4230/LIPIcs.ISAAC.2023.50}, annote = {Keywords: Unrelated Scheduling, Graph Balancing, Strict Correlation Constraints} }
Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)
Liang-Ting Chen and Hsiang-Shang Ko. Realising Intensional S4 and GL Modalities. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chen_et_al:LIPIcs.CSL.2022.14, author = {Chen, Liang-Ting and Ko, Hsiang-Shang}, title = {{Realising Intensional S4 and GL Modalities}}, booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)}, pages = {14:1--14:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-218-1}, ISSN = {1868-8969}, year = {2022}, volume = {216}, editor = {Manea, Florin and Simpson, Alex}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.14}, URN = {urn:nbn:de:0030-drops-157341}, doi = {10.4230/LIPIcs.CSL.2022.14}, annote = {Keywords: provability, guarded recursion, realisability, modal types, metaprogramming} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong. A Generalization of Self-Improving Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cheng_et_al:LIPIcs.SoCG.2020.29, author = {Cheng, Siu-Wing and Chiu, Man-Kwun and Jin, Kai and Wong, Man Ting}, title = {{A Generalization of Self-Improving Algorithms}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {29:1--29:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.29}, URN = {urn:nbn:de:0030-drops-121873}, doi = {10.4230/LIPIcs.SoCG.2020.29}, annote = {Keywords: expected running time, entropy, sorting, Delaunay triangulation} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Yen-Ting Chen, Meng-Tsung Tsai, and Shi-Chun Tsai. A Dichotomy Result for Cyclic-Order Traversing Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chen_et_al:LIPIcs.ISAAC.2018.29, author = {Chen, Yen-Ting and Tsai, Meng-Tsung and Tsai, Shi-Chun}, title = {{A Dichotomy Result for Cyclic-Order Traversing Games}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {29:1--29:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.29}, URN = {urn:nbn:de:0030-drops-99775}, doi = {10.4230/LIPIcs.ISAAC.2018.29}, annote = {Keywords: st-planar graphs, biconnectivity, fault-tolerant routing algorithms, software defined network} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Henning Urbat, Jiri Adámek, Liang-Ting Chen, and Stefan Milius. Eilenberg Theorems for Free. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{urbat_et_al:LIPIcs.MFCS.2017.43, author = {Urbat, Henning and Ad\'{a}mek, Jiri and Chen, Liang-Ting and Milius, Stefan}, title = {{Eilenberg Theorems for Free}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {43:1--43:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.43}, URN = {urn:nbn:de:0030-drops-81032}, doi = {10.4230/LIPIcs.MFCS.2017.43}, annote = {Keywords: Eilenberg's theorem, variety of languages, pseudovariety, monad, duality} }
Published in: LIPIcs, Volume 35, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)
Liang-Ting Chen and Henning Urbat. A Fibrational Approach to Automata Theory. In 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. 50-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{chen_et_al:LIPIcs.CALCO.2015.50, author = {Chen, Liang-Ting and Urbat, Henning}, title = {{A Fibrational Approach to Automata Theory}}, booktitle = {6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)}, pages = {50--65}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-84-2}, ISSN = {1868-8969}, year = {2015}, volume = {35}, editor = {Moss, Lawrence S. and Sobocinski, Pawel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2015.50}, URN = {urn:nbn:de:0030-drops-55268}, doi = {10.4230/LIPIcs.CALCO.2015.50}, annote = {Keywords: Eilenberg’s variety theorem, duality, coalgebra, Grothendieck fibration} }