Christoph Berkholz

According to our database, Christoph Berkholz authored at least 30 papers between 2012 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Boolean basis, formula size, and number of modal operators.

Christoph Berkholz, Dietrich Kuske, Christian Schwarz

CoRR, 2024

Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism.

Christoph Berkholz, Moritz Lichter, Harry Vinall-Smeeth

CoRR, 2024

A Characterization of Efficiently Compilable Constraint Languages.

Christoph Berkholz, Stefan Mengel, Hermann Wilhelm

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Modal Logic Is More Succinct Iff Bi-Implication Is Available in Some Form.

Christoph Berkholz, Dietrich Kuske, Christian Schwarz

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

2023

A Dichotomy for Succinct Representations of Homomorphisms.

Christoph Berkholz, Harry Vinall-Smeeth

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration.

Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Alessio Conte, Benny Kimelfeld, Nicole Schweikardt

ACM Trans. Database Syst., 2022

Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051).

Albert Atserias, Christoph Berkholz, Kousha Etessami, Joanna Ochremiak

Dagstuhl Reports, 2022

2021

Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration.

Christoph Berkholz, Maximilian Merz

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

2020

Constant delay enumeration for conjunctive queries: a tutorial.

Christoph Berkholz, Fabian Gerhardt, Nicole Schweikardt

ACM SIGLOG News, 2020

Supercritical Space-Width Trade-offs for Resolution.

Christoph Berkholz, Jakob Nordström

SIAM J. Comput., 2020

Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration.

Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, Nicole Schweikardt

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

2019

Compiling Existential Positive Queries to Bounded-Variable Fragments.

Christoph Berkholz, Hubie Chen

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width.

Christoph Berkholz, Nicole Schweikardt

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

Answering FO+MOD Queries under Updates on Bounded Degree Databases.

Christoph Berkholz, Jens Keppeler, Nicole Schweikardt

ACM Trans. Database Syst., 2018

On the speed of constraint propagation and the time complexity of arc consistency testing.

Christoph Berkholz, Oleg Verbitsky

J. Comput. Syst. Sci., 2018

Answering UCQs under Updates and in the Presence of Integrity Constraints.

Christoph Berkholz, Jens Keppeler, Nicole Schweikardt

Proceedings of the 21st International Conference on Database Theory, 2018

2017

Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement.

Christoph Berkholz, Paul S. Bonsma, Martin Grohe

Theory Comput. Syst., 2017

The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs.

Christoph Berkholz

Electron. Colloquium Comput. Complex., 2017

Linear Diophantine Equations, Group CSPs, and Graph Isomorphism.

Christoph Berkholz, Martin Grohe

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Answering Conjunctive Queries under Updates.

Christoph Berkholz, Jens Keppeler, Nicole Schweikardt

Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

2016

Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps.

Christoph Berkholz, Jakob Nordström

Electron. Colloquium Comput. Complex., 2016

2015

Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy.

Christoph Berkholz, Andreas Krebs, Oleg Verbitsky

ACM Trans. Comput. Log., 2015

Limitations of Algebraic Approaches to Graph Isomorphism Testing.

Christoph Berkholz, Martin Grohe

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Lower Bounds for Heuristic Algorithms.

Christoph Berkholz

PhD thesis, 2014

Untere Schranken für heuristische Algorithmen.

Christoph Berkholz

Proceedings of the Ausgezeichnete Informatikdissertationen 2014, 2014

Parameterized Complexity of Fixed Variable Logics.

Christoph Berkholz, Michael Elberfeld

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

The Propagation Depth of Local Consistency.

Christoph Berkholz

Proceedings of the Principles and Practice of Constraint Programming, 2014

2013

Lower Bounds for Existential Pebble Games and k-Consistency Tests

Christoph Berkholz

Log. Methods Comput. Sci., 2013

2012

Bounds for the quantifier depth in two-variable logic

Christoph Berkholz, Oleg Verbitsky

CoRR, 2012

On the Complexity of Finding Narrow Proofs.

Christoph Berkholz

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012