Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Marc Roth, Johannes Schmitt, and Philip Wellnitz. Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 108:1-108:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{roth_et_al:LIPIcs.ICALP.2021.108, author = {Roth, Marc and Schmitt, Johannes and Wellnitz, Philip}, title = {{Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {108:1--108:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.108}, URN = {urn:nbn:de:0030-drops-141778}, doi = {10.4230/LIPIcs.ICALP.2021.108}, annote = {Keywords: Counting complexity, parameterized complexity, Tutte polynomial} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, and Philip Wellnitz. Faster Minimization of Tardy Processing Time on a Single Machine. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 19:1-19:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bringmann_et_al:LIPIcs.ICALP.2020.19, author = {Bringmann, Karl and Fischer, Nick and Hermelin, Danny and Shabtay, Dvir and Wellnitz, Philip}, title = {{Faster Minimization of Tardy Processing Time on a Single Machine}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {19:1--19:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.19}, URN = {urn:nbn:de:0030-drops-124269}, doi = {10.4230/LIPIcs.ICALP.2020.19}, annote = {Keywords: Weighted number of tardy jobs, sumsets, convolutions} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 26:1-26:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{dorfler_et_al:LIPIcs.MFCS.2019.26, author = {D\"{o}rfler, Julian and Roth, Marc and Schmitt, Johannes and Wellnitz, Philip}, title = {{Counting Induced Subgraphs: An Algebraic Approach to #W\lbrack1\rbrack-hardness}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {26:1--26:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.26}, URN = {urn:nbn:de:0030-drops-109703}, doi = {10.4230/LIPIcs.MFCS.2019.26}, annote = {Keywords: counting complexity, edge-transitive graphs, graph homomorphisms, induced subgraphs, parameterized complexity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Holger Dell, Marc Roth, and Philip Wellnitz. Counting Answers to Existential Questions (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 113:1-113:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{dell_et_al:LIPIcs.ICALP.2019.113, author = {Dell, Holger and Roth, Marc and Wellnitz, Philip}, title = {{Counting Answers to Existential Questions}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {113:1--113:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.113}, URN = {urn:nbn:de:0030-drops-106894}, doi = {10.4230/LIPIcs.ICALP.2019.113}, annote = {Keywords: Conjunctive queries, graph homomorphisms, counting complexity, parameterized complexity, fine-grained complexity} }
Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Karl Bringmann and Philip Wellnitz. Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 12:1-12:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{bringmann_et_al:LIPIcs.CPM.2017.12, author = {Bringmann, Karl and Wellnitz, Philip}, title = {{Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars}}, booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)}, pages = {12:1--12:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-039-2}, ISSN = {1868-8969}, year = {2017}, volume = {78}, editor = {K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.12}, URN = {urn:nbn:de:0030-drops-73329}, doi = {10.4230/LIPIcs.CPM.2017.12}, annote = {Keywords: conditional lower bounds, k-Clique, parsing, tree-adjoining grammars} }
Feedback for Dagstuhl Publishing