Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Martin Grohe, Benny Kimelfeld, Peter Lindner, and Christoph Standke. The Importance of Parameters in Database Queries. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{grohe_et_al:LIPIcs.ICDT.2024.14, author = {Grohe, Martin and Kimelfeld, Benny and Lindner, Peter and Standke, Christoph}, title = {{The Importance of Parameters in Database Queries}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {14:1--14:17}, 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.14}, URN = {urn:nbn:de:0030-drops-197966}, doi = {10.4230/LIPIcs.ICDT.2024.14}, annote = {Keywords: SHAP score, query parameters, Shapley value} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Jan Böker, Louis Härtel, Nina Runde, Tim Seppelt, and Christoph Standke. The Complexity of Homomorphism Reconstructibility. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{boker_et_al:LIPIcs.STACS.2024.19, author = {B\"{o}ker, Jan and H\"{a}rtel, Louis and Runde, Nina and Seppelt, Tim and Standke, Christoph}, title = {{The Complexity of Homomorphism Reconstructibility}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {19:1--19:20}, 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.19}, URN = {urn:nbn:de:0030-drops-197298}, doi = {10.4230/LIPIcs.STACS.2024.19}, annote = {Keywords: graph homomorphism, counting complexity, parameterised complexity} }
Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Eva Fluck, Tim Seppelt, and Gian Luca Spitzer. Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fluck_et_al:LIPIcs.CSL.2024.27, author = {Fluck, Eva and Seppelt, Tim and Spitzer, Gian Luca}, title = {{Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {27:1--27:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.27}, URN = {urn:nbn:de:0030-drops-196704}, doi = {10.4230/LIPIcs.CSL.2024.27}, annote = {Keywords: Treewidth, treedepth, homomorphism indistinguishability, counting first-order logic} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Tim Seppelt. Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{seppelt:LIPIcs.MFCS.2023.82, author = {Seppelt, Tim}, title = {{Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {82:1--82: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.82}, URN = {urn:nbn:de:0030-drops-186161}, doi = {10.4230/LIPIcs.MFCS.2023.82}, annote = {Keywords: homomorphism indistinguishability, graph minor, logic} }
Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)
Martin Grohe, Peter Lindner, and Christoph Standke. Probabilistic Query Evaluation with Bag Semantics. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{grohe_et_al:LIPIcs.ICDT.2023.20, author = {Grohe, Martin and Lindner, Peter and Standke, Christoph}, title = {{Probabilistic Query Evaluation with Bag Semantics}}, booktitle = {26th International Conference on Database Theory (ICDT 2023)}, pages = {20:1--20:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-270-9}, ISSN = {1868-8969}, year = {2023}, volume = {255}, editor = {Geerts, Floris and Vandevoort, Brecht}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.20}, URN = {urn:nbn:de:0030-drops-177636}, doi = {10.4230/LIPIcs.ICDT.2023.20}, annote = {Keywords: Probabilistic Query Evaluation, Probabilistic Databases, Bag Semantics} }
Published in: Dagstuhl Reports, Volume 12, Issue 5 (2022)
Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). In Dagstuhl Reports, Volume 12, Issue 5, pp. 112-130, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{grohe_et_al:DagRep.12.5.112, author = {Grohe, Martin and Guruswami, Venkatesan and Marx, D\'{a}niel and \v{Z}ivn\'{y}, Stanislav}, title = {{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201)}}, pages = {112--130}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {5}, editor = {Grohe, Martin and Guruswami, Venkatesan and Marx, D\'{a}niel and \v{Z}ivn\'{y}, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.5.112}, URN = {urn:nbn:de:0030-drops-174453}, doi = {10.4230/DagRep.12.5.112}, annote = {Keywords: Constraint satisfaction problem (CSP); Computational complexity; Hardness of approximation; Universal algebra; Semidefinite programming} }
Published in: Dagstuhl Reports, Volume 12, Issue 3 (2022)
Martin Grohe, Stephan Günnemann, Stefanie Jegelka, and Christopher Morris. Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132). In Dagstuhl Reports, Volume 12, Issue 3, pp. 141-155, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{grohe_et_al:DagRep.12.3.141, author = {Grohe, Martin and G\"{u}nnemann, Stephan and Jegelka, Stefanie and Morris, Christopher}, title = {{Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132)}}, pages = {141--155}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {3}, editor = {Grohe, Martin and G\"{u}nnemann, Stephan and Jegelka, Stefanie and Morris, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.3.141}, URN = {urn:nbn:de:0030-drops-172727}, doi = {10.4230/DagRep.12.3.141}, annote = {Keywords: Machine Learning For Graphs, GNNs, Graph Embedding} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Timo Gervens and Martin Grohe. Graph Similarity Based on Matrix Norms. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gervens_et_al:LIPIcs.MFCS.2022.52, author = {Gervens, Timo and Grohe, Martin}, title = {{Graph Similarity Based on Matrix Norms}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {52:1--52:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.52}, URN = {urn:nbn:de:0030-drops-168509}, doi = {10.4230/LIPIcs.MFCS.2022.52}, annote = {Keywords: graph similarity, approximate graph isomorphism, graph matching} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism Tensors and Linear Equations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{grohe_et_al:LIPIcs.ICALP.2022.70, author = {Grohe, Martin and Rattan, Gaurav and Seppelt, Tim}, title = {{Homomorphism Tensors and Linear Equations}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {70:1--70: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.70}, URN = {urn:nbn:de:0030-drops-164113}, doi = {10.4230/LIPIcs.ICALP.2022.70}, annote = {Keywords: homomorphisms, labelled graphs, treewidth, pathwidth, treedepth, linear equations, Sherali-Adams relaxation, Wiegmann-Specht Theorem, Weisfeiler-Leman} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Martin Grohe. A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grohe:LIPIcs.MFCS.2021.2, author = {Grohe, Martin}, title = {{A Deep Dive into the Weisfeiler-Leman Algorithm}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {2:1--2:1}, 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.2}, URN = {urn:nbn:de:0030-drops-144429}, doi = {10.4230/LIPIcs.MFCS.2021.2}, annote = {Keywords: Weisfeiler-Leman algorithm, graph isomorphism, counting homomorphisms, finite variable logics} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Anuj Dawar and Danny Vagnozzi. On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dawar_et_al:LIPIcs.MFCS.2021.37, author = {Dawar, Anuj and Vagnozzi, Danny}, title = {{On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {37:1--37:16}, 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.37}, URN = {urn:nbn:de:0030-drops-144774}, doi = {10.4230/LIPIcs.MFCS.2021.37}, annote = {Keywords: Graph isomorphism, proof complexity, invertible map tests} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Martin Grohe and Sandra Kiefer. Logarithmic Weisfeiler-Leman Identifies All Planar Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 134:1-134:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grohe_et_al:LIPIcs.ICALP.2021.134, author = {Grohe, Martin and Kiefer, Sandra}, title = {{Logarithmic Weisfeiler-Leman Identifies All Planar Graphs}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {134:1--134:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.134}, URN = {urn:nbn:de:0030-drops-142035}, doi = {10.4230/LIPIcs.ICALP.2021.134}, annote = {Keywords: Weisfeiler-Leman algorithm, finite-variable logic, isomorphism testing, planar graphs, quantifier depth, iteration number} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, and Muhammad Tibi. Database Repairing with Soft Functional Dependencies. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{carmeli_et_al:LIPIcs.ICDT.2021.16, author = {Carmeli, Nofar and Grohe, Martin and Kimelfeld, Benny and Livshits, Ester and Tibi, Muhammad}, title = {{Database Repairing with Soft Functional Dependencies}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {16:1--16:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.16}, URN = {urn:nbn:de:0030-drops-137245}, doi = {10.4230/LIPIcs.ICDT.2021.16}, annote = {Keywords: Database inconsistency, database repairs, integrity constraints, soft constraints, functional dependencies} }
Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Steffen van Bergerem and Nicole Schweikardt. Learning Concepts Described By Weight Aggregation Logic. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{vanbergerem_et_al:LIPIcs.CSL.2021.10, author = {van Bergerem, Steffen and Schweikardt, Nicole}, title = {{Learning Concepts Described By Weight Aggregation Logic}}, booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-175-7}, ISSN = {1868-8969}, year = {2021}, volume = {183}, editor = {Baier, Christel and Goubault-Larrecq, Jean}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.10}, URN = {urn:nbn:de:0030-drops-134447}, doi = {10.4230/LIPIcs.CSL.2021.10}, annote = {Keywords: first-order definable concept learning, agnostic probably approximately correct learning, classification problems, locality, Feferman-Vaught decomposition, Gaifman normal form, first-order logic with counting, weight aggregation logic} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Artem Govorov, Jin-Yi Cai, and Martin Dyer. A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{govorov_et_al:LIPIcs.ICALP.2020.66, author = {Govorov, Artem and Cai, Jin-Yi and Dyer, Martin}, title = {{A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {66:1--66:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.66}, URN = {urn:nbn:de:0030-drops-124733}, doi = {10.4230/LIPIcs.ICALP.2020.66}, annote = {Keywords: Graph homomorphism, Complexity dichotomy, Counting problems} }
Feedback for Dagstuhl Publishing