Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Christoph Berkholz, Stefan Mengel, and Hermann Wilhelm. A Characterization of Efficiently Compilable Constraint Languages. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{berkholz_et_al:LIPIcs.STACS.2024.11, author = {Berkholz, Christoph and Mengel, Stefan and Wilhelm, Hermann}, title = {{A Characterization of Efficiently Compilable Constraint Languages}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {11:1--11:19}, 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.11}, URN = {urn:nbn:de:0030-drops-197214}, doi = {10.4230/LIPIcs.STACS.2024.11}, annote = {Keywords: constraint satisfaction, knowledge compilation, dichotomy, DNNF} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Christoph Berkholz, Dietrich Kuske, and Christian Schwarz. Modal Logic Is More Succinct Iff Bi-Implication Is Available in Some Form. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{berkholz_et_al:LIPIcs.STACS.2024.12, author = {Berkholz, Christoph and Kuske, Dietrich and Schwarz, Christian}, title = {{Modal Logic Is More Succinct Iff Bi-Implication Is Available in Some Form}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {12:1--12: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.12}, URN = {urn:nbn:de:0030-drops-197228}, doi = {10.4230/LIPIcs.STACS.2024.12}, annote = {Keywords: succinctness, modal logic} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Christoph Berkholz and Harry Vinall-Smeeth. A Dichotomy for Succinct Representations of Homomorphisms. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 113:1-113:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{berkholz_et_al:LIPIcs.ICALP.2023.113, author = {Berkholz, Christoph and Vinall-Smeeth, Harry}, title = {{A Dichotomy for Succinct Representations of Homomorphisms}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {113:1--113:19}, 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.113}, URN = {urn:nbn:de:0030-drops-181653}, doi = {10.4230/LIPIcs.ICALP.2023.113}, annote = {Keywords: homomorphism problem, CSP, succinct representations, enumeration, lower bound, treewidth} }
Published in: Dagstuhl Reports, Volume 12, Issue 1 (2022)
Albert Atserias, Christoph Berkholz, Kousha Etessami, and Joanna Ochremiak. Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051). In Dagstuhl Reports, Volume 12, Issue 1, pp. 101-118, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{atserias_et_al:DagRep.12.1.101, author = {Atserias, Albert and Berkholz, Christoph and Etessami, Kousha and Ochremiak, Joanna}, title = {{Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051)}}, pages = {101--118}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {1}, editor = {Atserias, Albert and Berkholz, Christoph and Etessami, Kousha and Ochremiak, Joanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.1.101}, URN = {urn:nbn:de:0030-drops-169232}, doi = {10.4230/DagRep.12.1.101}, annote = {Keywords: automata and game theory, database theory, descriptive complexity, finite model theory, homomorphism counts, Query enumeration} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Christoph Berkholz and Nicole Schweikardt. Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{berkholz_et_al:LIPIcs.MFCS.2019.58, author = {Berkholz, Christoph and Schweikardt, Nicole}, title = {{Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {58:1--58:15}, 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.58}, URN = {urn:nbn:de:0030-drops-110021}, doi = {10.4230/LIPIcs.MFCS.2019.58}, annote = {Keywords: conjunctive queries, constant delay enumeration, hypertree decompositions, submodular width, fixed-parameter tractability} }
Published in: LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018)
Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering UCQs under Updates and in the Presence of Integrity Constraints. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{berkholz_et_al:LIPIcs.ICDT.2018.8, author = {Berkholz, Christoph and Keppeler, Jens and Schweikardt, Nicole}, title = {{Answering UCQs under Updates and in the Presence of Integrity Constraints}}, booktitle = {21st International Conference on Database Theory (ICDT 2018)}, pages = {8:1--8:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-063-7}, ISSN = {1868-8969}, year = {2018}, volume = {98}, editor = {Kimelfeld, Benny and Amsterdamer, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.8}, URN = {urn:nbn:de:0030-drops-85990}, doi = {10.4230/LIPIcs.ICDT.2018.8}, annote = {Keywords: dynamic query evaluation, union of conjunctive queries, constant-delay enumeration, counting problem, testing} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Christoph Berkholz. The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{berkholz:LIPIcs.STACS.2018.11, author = {Berkholz, Christoph}, title = {{The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf 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.2018.11}, URN = {urn:nbn:de:0030-drops-85279}, doi = {10.4230/LIPIcs.STACS.2018.11}, annote = {Keywords: Proof Complexity, Polynomial Calculus, Sum-of-Squares, Sherali-Adams} }
Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)
Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering FO+MOD Queries Under Updates on Bounded Degree Databases. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{berkholz_et_al:LIPIcs.ICDT.2017.8, author = {Berkholz, Christoph and Keppeler, Jens and Schweikardt, Nicole}, title = {{Answering FO+MOD Queries Under Updates on Bounded Degree Databases}}, booktitle = {20th International Conference on Database Theory (ICDT 2017)}, pages = {8:1--8:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-024-8}, ISSN = {1868-8969}, year = {2017}, volume = {68}, editor = {Benedikt, Michael and Orsi, Giorgio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.8}, URN = {urn:nbn:de:0030-drops-70535}, doi = {10.4230/LIPIcs.ICDT.2017.8}, annote = {Keywords: dynamic databases, query enumeration, counting problem, first-order logic with modulo-counting quantifiers, Hanf locality} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Christoph Berkholz and Jakob Nordström. Supercritical Space-Width Trade-Offs for Resolution. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{berkholz_et_al:LIPIcs.ICALP.2016.57, author = {Berkholz, Christoph and Nordstr\"{o}m, Jakob}, title = {{Supercritical Space-Width Trade-Offs for Resolution}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {57:1--57: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.57}, URN = {urn:nbn:de:0030-drops-62266}, doi = {10.4230/LIPIcs.ICALP.2016.57}, annote = {Keywords: Proof complexity, resolution, space, width, trade-offs, supercritical} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Christoph Berkholz and Michael Elberfeld. Parameterized Complexity of Fixed Variable Logics. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 109-120, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{berkholz_et_al:LIPIcs.FSTTCS.2014.109, author = {Berkholz, Christoph and Elberfeld, Michael}, title = {{Parameterized Complexity of Fixed Variable Logics}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {109--120}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.109}, URN = {urn:nbn:de:0030-drops-48367}, doi = {10.4230/LIPIcs.FSTTCS.2014.109}, annote = {Keywords: Parameterized complexity, polynomial space, first-order logic, pebble games, regular resolutions} }
Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)
Christoph Berkholz, Andreas Krebs, and Oleg Verbitsky. Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 61-80, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{berkholz_et_al:LIPIcs.CSL.2013.61, author = {Berkholz, Christoph and Krebs, Andreas and Verbitsky, Oleg}, title = {{Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy}}, booktitle = {Computer Science Logic 2013 (CSL 2013)}, pages = {61--80}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-60-6}, ISSN = {1868-8969}, year = {2013}, volume = {23}, editor = {Ronchi Della Rocca, Simona}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.61}, URN = {urn:nbn:de:0030-drops-41907}, doi = {10.4230/LIPIcs.CSL.2013.61}, annote = {Keywords: Alternation hierarchy, finite-variable logic} }
Feedback for Dagstuhl Publishing