Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Leslie Ann Goldberg and Marc Roth. Parameterised and Fine-Grained Subgraph Counting, Modulo 2. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 68:1-68:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{goldberg_et_al:LIPIcs.ICALP.2023.68, author = {Goldberg, Leslie Ann and Roth, Marc}, title = {{Parameterised and Fine-Grained Subgraph Counting, Modulo 2}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {68:1--68:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.68}, URN = {urn:nbn:de:0030-drops-181200}, doi = {10.4230/LIPIcs.ICALP.2023.68}, annote = {Keywords: modular counting, parameterised complexity, fine-grained complexity, subgraph counting} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Radu Curticapean, Nutan Limaye, and Srikanth Srinivasan. On the VNP-Hardness of Some Monomial Symmetric Polynomials. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{curticapean_et_al:LIPIcs.FSTTCS.2022.16, author = {Curticapean, Radu and Limaye, Nutan and Srinivasan, Srikanth}, title = {{On the VNP-Hardness of Some Monomial Symmetric Polynomials}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {16:1--16:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.16}, URN = {urn:nbn:de:0030-drops-174081}, doi = {10.4230/LIPIcs.FSTTCS.2022.16}, annote = {Keywords: algebraic complexity, symmetric polynomial, permanent, Sidon set} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Radu Curticapean. Determinants from Homomorphisms. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 38:1-38:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{curticapean:LIPIcs.ESA.2022.38, author = {Curticapean, Radu}, title = {{Determinants from Homomorphisms}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {38:1--38:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.38}, URN = {urn:nbn:de:0030-drops-169767}, doi = {10.4230/LIPIcs.ESA.2022.38}, annote = {Keywords: determinant, homomorphisms, matrix trace, Newton identities} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Radu Curticapean, Holger Dell, and Thore Husfeldt. Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{curticapean_et_al:LIPIcs.ESA.2021.34, author = {Curticapean, Radu and Dell, Holger and Husfeldt, Thore}, title = {{Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {34:1--34:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.34}, URN = {urn:nbn:de:0030-drops-146154}, doi = {10.4230/LIPIcs.ESA.2021.34}, annote = {Keywords: Counting complexity, matchings, paths, subgraphs, parameterized complexity} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, and Alina Vdovina. Parameterized (Modular) Counting and Cayley Graph Expanders. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 84:1-84:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{peyerimhoff_et_al:LIPIcs.MFCS.2021.84, author = {Peyerimhoff, Norbert and Roth, Marc and Schmitt, Johannes and Stix, Jakob and Vdovina, Alina}, title = {{Parameterized (Modular) Counting and Cayley Graph Expanders}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {84:1--84:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.84}, URN = {urn:nbn:de:0030-drops-145246}, doi = {10.4230/LIPIcs.MFCS.2021.84}, annote = {Keywords: Cayley graphs, counting complexity, expander graphs, fine-grained complexity, parameterized complexity} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Markus Bläser and Christian Engels. Parameterized Valiant’s Classes. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{blaser_et_al:LIPIcs.IPEC.2019.3, author = {Bl\"{a}ser, Markus and Engels, Christian}, title = {{Parameterized Valiant’s Classes}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {3:1--3:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.3}, URN = {urn:nbn:de:0030-drops-114648}, doi = {10.4230/LIPIcs.IPEC.2019.3}, annote = {Keywords: Algebraic complexity theory, parameterized complexity theory, Valiant’s classes} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh. Parameterized Streaming Algorithms for Min-Ones d-SAT. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2019.8, author = {Agrawal, Akanksha and Biswas, Arindam and Bonnet, \'{E}douard and Brettell, Nick and Curticapean, Radu and Marx, D\'{a}niel and Miltzow, Tillmann and Raman, Venkatesh and Saurabh, Saket}, title = {{Parameterized Streaming Algorithms for Min-Ones d-SAT}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.8}, URN = {urn:nbn:de:0030-drops-115708}, doi = {10.4230/LIPIcs.FSTTCS.2019.8}, annote = {Keywords: min, ones, sat, d-sat, parameterized, kernelization, streaming, space, efficient, algorithm, parameter} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Cornelius Brand. Patching Colors with Tensors. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{brand:LIPIcs.ESA.2019.25, author = {Brand, Cornelius}, title = {{Patching Colors with Tensors}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {25:1--25:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.25}, URN = {urn:nbn:de:0030-drops-111467}, doi = {10.4230/LIPIcs.ESA.2019.25}, annote = {Keywords: Color-Coding, Extensor-Coding, internal out-branching, colorful problems, algebraic algorithms, multilinear detection, deterministic algorithms, exterior algebra} }
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-dev.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-dev.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 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Radu Curticapean. Counting Problems in Parameterized Complexity. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{curticapean:LIPIcs.IPEC.2018.1, author = {Curticapean, Radu}, title = {{Counting Problems in Parameterized Complexity}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {1:1--1:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.1}, URN = {urn:nbn:de:0030-drops-102026}, doi = {10.4230/LIPIcs.IPEC.2018.1}, annote = {Keywords: counting complexity, parameterized complexity, graph motifs, perfect matchings, graph minor theory, Hamiltonian cycles} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, and John Lapinskas. A Fixed-Parameter Perspective on #BIS. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{curticapean_et_al:LIPIcs.IPEC.2017.13, author = {Curticapean, Radu and Dell, Holger and Fomin, Fedor V. and Goldberg, Leslie Ann and Lapinskas, John}, title = {{A Fixed-Parameter Perspective on #BIS}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.13}, URN = {urn:nbn:de:0030-drops-85613}, doi = {10.4230/LIPIcs.IPEC.2017.13}, annote = {Keywords: Approximate counting, parameterised complexity, independent sets} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding Detours is Fixed-Parameter Tractable. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bezakova_et_al:LIPIcs.ICALP.2017.54, author = {Bez\'{a}kov\'{a}, Ivona and Curticapean, Radu and Dell, Holger and Fomin, Fedor V.}, title = {{Finding Detours is Fixed-Parameter Tractable}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {54:1--54:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian 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.ICALP.2017.54}, URN = {urn:nbn:de:0030-drops-74790}, doi = {10.4230/LIPIcs.ICALP.2017.54}, annote = {Keywords: longest path, fixed-parameter tractable algorithms, above-guarantee parameterization, graph minors} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Radu Curticapean, Holger Dell, and Marc Roth. Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{curticapean_et_al:LIPIcs.STACS.2017.25, author = {Curticapean, Radu and Dell, Holger and Roth, Marc}, title = {{Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {25:1--25:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.25}, URN = {urn:nbn:de:0030-drops-70080}, doi = {10.4230/LIPIcs.STACS.2017.25}, annote = {Keywords: matchings, homomorphisms, line graphs, counting complexity, parameterized complexity} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Radu Curticapean. Parity Separation: A Scientifically Proven Method for Permanent Weight Loss. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{curticapean:LIPIcs.ICALP.2016.47, author = {Curticapean, Radu}, title = {{Parity Separation: A Scientifically Proven Method for Permanent Weight Loss}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {47:1--47:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.47}, URN = {urn:nbn:de:0030-drops-63279}, doi = {10.4230/LIPIcs.ICALP.2016.47}, annote = {Keywords: perfect matchings, counting complexity, structural complexity, exponentialtime hypothesis} }
Feedback for Dagstuhl Publishing