![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
default search action
Christoph Berkholz
Person information
- affiliation: Humboldt-Universität zu Berlin
Refine list
![note](https://dblp1.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Books and Theses
- 2014
- [b1]Christoph Berkholz:
Lower Bounds for Heuristic Algorithms. RWTH Aachen University, Germany, 2014
Journal Articles
- 2023
- [j9]Christoph Berkholz, Jakob Nordström:
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. J. ACM 70(5): 32:1-32:32 (2023) - 2022
- [j8]Nofar Carmeli
, Shai Zeevi
, Christoph Berkholz
, Alessio Conte
, Benny Kimelfeld
, Nicole Schweikardt
:
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration. ACM Trans. Database Syst. 47(3): 9:1-9:49 (2022) - 2020
- [j7]Christoph Berkholz, Jakob Nordström
:
Supercritical Space-Width Trade-offs for Resolution. SIAM J. Comput. 49(1): 98-118 (2020) - [j6]Christoph Berkholz, Fabian Gerhardt, Nicole Schweikardt:
Constant delay enumeration for conjunctive queries: a tutorial. ACM SIGLOG News 7(1): 4-33 (2020) - 2018
- [j5]Christoph Berkholz, Oleg Verbitsky
:
On the speed of constraint propagation and the time complexity of arc consistency testing. J. Comput. Syst. Sci. 91: 104-114 (2018) - [j4]Christoph Berkholz, Jens Keppeler, Nicole Schweikardt:
Answering FO+MOD Queries under Updates on Bounded Degree Databases. ACM Trans. Database Syst. 43(2): 7:1-7:32 (2018) - 2017
- [j3]Christoph Berkholz, Paul S. Bonsma, Martin Grohe:
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. Theory Comput. Syst. 60(4): 581-614 (2017) - 2015
- [j2]Christoph Berkholz, Andreas Krebs, Oleg Verbitsky:
Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy. ACM Trans. Comput. Log. 16(3): 21:1-21:26 (2015) - 2013
- [j1]Christoph Berkholz:
Lower Bounds for Existential Pebble Games and k-Consistency Tests. Log. Methods Comput. Sci. 9(4) (2013)
Conference and Workshop Papers
- 2024
- [c22]Christoph Berkholz, Stefan Mengel, Hermann Wilhelm:
A Characterization of Efficiently Compilable Constraint Languages. STACS 2024: 11:1-11:19 - [c21]Christoph Berkholz, Dietrich Kuske, Christian Schwarz:
Modal Logic Is More Succinct Iff Bi-Implication Is Available in Some Form. STACS 2024: 12:1-12:17 - 2023
- [c20]Christoph Berkholz, Harry Vinall-Smeeth
:
A Dichotomy for Succinct Representations of Homomorphisms. ICALP 2023: 113:1-113:19 - 2021
- [c19]Christoph Berkholz, Maximilian Merz:
Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration. PODS 2021: 402-415 - 2020
- [c18]Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, Nicole Schweikardt:
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration. PODS 2020: 393-409 - 2019
- [c17]Christoph Berkholz, Nicole Schweikardt:
Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width. MFCS 2019: 58:1-58:15 - [c16]Christoph Berkholz, Hubie Chen:
Compiling Existential Positive Queries to Bounded-Variable Fragments. PODS 2019: 353-364 - 2018
- [c15]Christoph Berkholz, Jens Keppeler, Nicole Schweikardt:
Answering UCQs under Updates and in the Presence of Integrity Constraints. ICDT 2018: 8:1-8:19 - [c14]Christoph Berkholz:
The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs. STACS 2018: 11:1-11:14 - 2017
- [c13]Christoph Berkholz, Jens Keppeler, Nicole Schweikardt:
Answering FO+MOD Queries Under Updates on Bounded Degree Databases. ICDT 2017: 8:1-8:18 - [c12]Christoph Berkholz, Jens Keppeler, Nicole Schweikardt:
Answering Conjunctive Queries under Updates. PODS 2017: 303-318 - [c11]Christoph Berkholz, Martin Grohe:
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism. SODA 2017: 327-339 - 2016
- [c10]Christoph Berkholz, Jakob Nordström
:
Supercritical Space-Width Trade-Offs for Resolution. ICALP 2016: 57:1-57:14 - [c9]Christoph Berkholz, Jakob Nordström
:
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. LICS 2016: 267-276 - 2015
- [c8]Christoph Berkholz, Martin Grohe
:
Limitations of Algebraic Approaches to Graph Isomorphism Testing. ICALP (1) 2015: 155-166 - 2014
- [c7]Christoph Berkholz:
The Propagation Depth of Local Consistency. CP 2014: 158-173 - [c6]Christoph Berkholz, Michael Elberfeld:
Parameterized Complexity of Fixed Variable Logics. FSTTCS 2014: 109-120 - 2013
- [c5]Christoph Berkholz, Andreas Krebs, Oleg Verbitsky:
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. CSL 2013: 61-80 - [c4]Christoph Berkholz, Paul S. Bonsma, Martin Grohe
:
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. ESA 2013: 145-156 - [c3]Christoph Berkholz, Oleg Verbitsky
:
On the Speed of Constraint Propagation and the Time Complexity of Arc Consistency Testing. MFCS 2013: 159-170 - 2012
- [c2]Christoph Berkholz:
On the Complexity of Finding Narrow Proofs. FOCS 2012: 351-360 - [c1]Christoph Berkholz:
Lower Bounds for Existential Pebble Games and k-Consistency Tests. LICS 2012: 25-34
Parts in Books or Collections
- 2014
- [p1]Christoph Berkholz:
Untere Schranken für heuristische Algorithmen. Ausgezeichnete Informatikdissertationen 2014: 31-40
Informal and Other Publications
- 2023
- [i20]Christoph Berkholz, Stefan Mengel, Hermann Wilhelm:
A characterization of efficiently compilable constraint languages. CoRR abs/2311.10040 (2023) - 2022
- [i19]Christoph Berkholz, Harry Vinall-Smeeth:
A dichotomy for succinct representations of homomorphisms. CoRR abs/2209.14662 (2022) - [i18]Albert Atserias, Christoph Berkholz, Kousha Etessami, Joanna Ochremiak:
Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051). Dagstuhl Reports 12(1): 101-118 (2022) - 2020
- [i17]Christoph Berkholz, Nicole Schweikardt:
Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width. CoRR abs/2003.01075 (2020) - 2019
- [i16]Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, Nicole Schweikardt:
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration. CoRR abs/1912.10704 (2019) - 2017
- [i15]Christoph Berkholz, Jens Keppeler, Nicole Schweikardt:
Answering Conjunctive Queries under Updates. CoRR abs/1702.06370 (2017) - [i14]Christoph Berkholz, Jens Keppeler, Nicole Schweikardt:
Answering FO+MOD queries under updates on bounded degree databases. CoRR abs/1702.08764 (2017) - [i13]Christoph Berkholz, Jens Keppeler, Nicole Schweikardt:
Answering UCQs under updates and in the presence of integrity constraints. CoRR abs/1709.10039 (2017) - [i12]Christoph Berkholz:
The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i11]Christoph Berkholz, Martin Grohe:
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism. CoRR abs/1607.04287 (2016) - [i10]Christoph Berkholz, Jakob Nordström:
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. CoRR abs/1608.08704 (2016) - [i9]Christoph Berkholz, Jakob Nordström:
Supercritical Space-Width Trade-offs for Resolution. CoRR abs/1612.07162 (2016) - [i8]Christoph Berkholz, Jakob Nordström:
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. Electron. Colloquium Comput. Complex. TR16 (2016) - [i7]Christoph Berkholz, Jakob Nordström:
Supercritical Space-Width Trade-offs for Resolution. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i6]Christoph Berkholz, Martin Grohe:
Limitations of Algebraic Approaches to Graph Isomorphism Testing. CoRR abs/1502.05912 (2015) - [i5]Christoph Berkholz, Paul S. Bonsma, Martin Grohe:
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. CoRR abs/1509.08251 (2015) - 2014
- [i4]Christoph Berkholz:
The Propagation Depth of Local Consistency. CoRR abs/1406.4679 (2014) - 2013
- [i3]Christoph Berkholz, Oleg Verbitsky:
On the speed of constraint propagation and the time complexity of arc consistency testing. CoRR abs/1303.7077 (2013) - 2012
- [i2]Christoph Berkholz:
On the complexity of finding narrow proofs. CoRR abs/1204.0775 (2012) - [i1]Christoph Berkholz, Oleg Verbitsky:
Bounds for the quantifier depth in two-variable logic. CoRR abs/1212.2747 (2012)
Coauthor Index
![](https://dblp1.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-05 21:13 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint