Christoph Berkholz

59 papers A* 10A 8B 4Journal 33Unranked 2

Year	Rank	Type	Title / Venue / Authors
2026	A	`conf`	Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy. ICDT Christoph Berkholz, Harry Vinall-Smeeth
2025	J	`jnl`	Boolean basis, formula size, and number of modal operators. Log. Methods Comput. Sci. Christoph Berkholz, Dietrich Kuske, Christian Schwarz
2025	J	`jnl`	Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy. CoRR Christoph Berkholz, Harry Vinall-Smeeth
2025	B	`conf`	Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism. MFCS Christoph Berkholz, Moritz Lichter, Harry Vinall-Smeeth
2024	A	`conf`	A Characterization of Efficiently Compilable Constraint Languages. STACS Christoph Berkholz, Stefan Mengel, Hermann Wilhelm
2024	J	`jnl`	Boolean basis, formula size, and number of modal operators. CoRR Christoph Berkholz, Dietrich Kuske, Christian Schwarz
2024	A	`conf`	Modal Logic Is More Succinct Iff Bi-Implication Is Available in Some Form. STACS Christoph Berkholz, Dietrich Kuske, Christian Schwarz
2024	J	`jnl`	Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism. CoRR Christoph Berkholz, Moritz Lichter, Harry Vinall-Smeeth
2023	A*	`conf`	A Dichotomy for Succinct Representations of Homomorphisms. ICALP Christoph Berkholz, Harry Vinall-Smeeth
2023	J	`jnl`	A characterization of efficiently compilable constraint languages. CoRR Christoph Berkholz, Stefan Mengel, Hermann Wilhelm
2023	J	`jnl`	Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. J. ACM Christoph Berkholz, Jakob Nordström
2022	J	`jnl`	A dichotomy for succinct representations of homomorphisms. CoRR Christoph Berkholz, Harry Vinall-Smeeth
2022	J	`jnl`	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration. ACM Trans. Database Syst. Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Alessio Conte, Benny Kimelfeld, Nicole Schweikardt
2022	J	`jnl`	Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051). Dagstuhl Reports Albert Atserias, Christoph Berkholz, Kousha Etessami, Joanna Ochremiak
2021	A*	`conf`	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration. PODS Christoph Berkholz, Maximilian Merz
2020	A*	`conf`	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration. PODS Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, Nicole Schweikardt
2020	J	`jnl`	Constant delay enumeration for conjunctive queries: a tutorial. ACM SIGLOG News Christoph Berkholz, Fabian Gerhardt, Nicole Schweikardt
2020	J	`jnl`	Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width. CoRR Christoph Berkholz, Nicole Schweikardt
2020	J	`jnl`	Supercritical Space-Width Trade-offs for Resolution. SIAM J. Comput. Christoph Berkholz, Jakob Nordström
2019	J	`jnl`	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration. CoRR Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, Nicole Schweikardt
2019	A*	`conf`	Compiling Existential Positive Queries to Bounded-Variable Fragments. PODS Christoph Berkholz, Hubie Chen
2019	B	`conf`	Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width. MFCS Christoph Berkholz, Nicole Schweikardt
2018	J	`jnl`	Answering FO+MOD Queries under Updates on Bounded Degree Databases. ACM Trans. Database Syst. Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
2018	A	`conf`	Answering UCQs under Updates and in the Presence of Integrity Constraints. ICDT Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
2018	J	`jnl`	On the speed of constraint propagation and the time complexity of arc consistency testing. J. Comput. Syst. Sci. Christoph Berkholz, Oleg Verbitsky
2018	A	`conf`	The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs. STACS Christoph Berkholz
2017	A*	`conf`	Answering Conjunctive Queries under Updates. PODS Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
2017	J	`jnl`	Answering Conjunctive Queries under Updates. CoRR Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
2017	A	`conf`	Answering FO+MOD Queries Under Updates on Bounded Degree Databases. ICDT Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
2017	J	`jnl`	Answering FO+MOD queries under updates on bounded degree databases. CoRR Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
2017	J	`jnl`	Answering UCQs under updates and in the presence of integrity constraints. CoRR Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
2017	A*	`conf`	Linear Diophantine Equations, Group CSPs, and Graph Isomorphism. SODA Christoph Berkholz, Martin Grohe
2017	J	`jnl`	The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs. Electron. Colloquium Comput. Complex. Christoph Berkholz
2017	J	`jnl`	Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. Theory Comput. Syst. Christoph Berkholz, Paul S. Bonsma, Martin Grohe
2016	J	`jnl`	Linear Diophantine Equations, Group CSPs, and Graph Isomorphism. CoRR Christoph Berkholz, Martin Grohe
2016	A*	`conf`	Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. LICS Christoph Berkholz, Jakob Nordström
2016	J	`jnl`	Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. CoRR Christoph Berkholz, Jakob Nordström
2016	J	`jnl`	Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. Electron. Colloquium Comput. Complex. Christoph Berkholz, Jakob Nordström
2016	A*	`conf`	Supercritical Space-Width Trade-Offs for Resolution. ICALP Christoph Berkholz, Jakob Nordström
2016	J	`jnl`	Supercritical Space-Width Trade-offs for Resolution. CoRR Christoph Berkholz, Jakob Nordström
2016	J	`jnl`	Supercritical Space-Width Trade-offs for Resolution. Electron. Colloquium Comput. Complex. Christoph Berkholz, Jakob Nordström
2015	J	`jnl`	Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy. ACM Trans. Comput. Log. Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
2015	—	`conf`	Limitations of Algebraic Approaches to Graph Isomorphism Testing. ICALP (1) Christoph Berkholz, Martin Grohe
2015	J	`jnl`	Limitations of Algebraic Approaches to Graph Isomorphism Testing. CoRR Christoph Berkholz, Martin Grohe
2015	J	`jnl`	Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. CoRR Christoph Berkholz, Paul S. Bonsma, Martin Grohe
2014	—	`—`	Lower Bounds for Heuristic Algorithms. Christoph Berkholz
2014	—	`conf`	Parameterized Complexity of Fixed Variable Logics. FSTTCS Christoph Berkholz, Michael Elberfeld
2014	A	`conf`	The Propagation Depth of Local Consistency. CP Christoph Berkholz
2014	J	`jnl`	The Propagation Depth of Local Consistency. CoRR Christoph Berkholz
2014	—	`ch.`	Untere Schranken für heuristische Algorithmen. Ausgezeichnete Informatikdissertationen Christoph Berkholz
2013	B	`conf`	Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. CSL Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
2013	J	`jnl`	Lower Bounds for Existential Pebble Games and k-Consistency Tests Log. Methods Comput. Sci. Christoph Berkholz
2013	B	`conf`	On the Speed of Constraint Propagation and the Time Complexity of Arc Consistency Testing. MFCS Christoph Berkholz, Oleg Verbitsky
2013	J	`jnl`	On the speed of constraint propagation and the time complexity of arc consistency testing CoRR Christoph Berkholz, Oleg Verbitsky
2013	A	`conf`	Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. ESA Christoph Berkholz, Paul S. Bonsma, Martin Grohe
2012	J	`jnl`	Bounds for the quantifier depth in two-variable logic CoRR Christoph Berkholz, Oleg Verbitsky
2012	A*	`conf`	Lower Bounds for Existential Pebble Games and k-Consistency Tests. LICS Christoph Berkholz
2012	A*	`conf`	On the Complexity of Finding Narrow Proofs. FOCS Christoph Berkholz
2012	J	`jnl`	On the complexity of finding narrow proofs CoRR Christoph Berkholz