Christoph Berkholz

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
A dichotomy for succinct representations of homomorphisms	2024-11-14	Paper
Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width	2022-07-21	Paper
Answering FO+MOD queries under updates on bounded degree databases ACM Transactions on Database Systems	2021-11-25	Paper
Answering UCQs under updates and in the presence of integrity constraints	2020-08-06	Paper
The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs	2020-08-05	Paper
Supercritical space-width trade-offs for resolution SIAM Journal on Computing	2020-02-12	Paper
Answering FO+MOD queries under updates on bounded degree databases	2018-07-18	Paper
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms	2018-07-16	Paper
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science	2018-04-23	Paper
Supercritical space-width trade-offs for resolution	2017-12-19	Paper
On the speed of constraint propagation and the time complexity of arc consistency testing Journal of Computer and System Sciences	2017-10-11	Paper
Tight lower and upper bounds for the complexity of canonical colour refinement Theory of Computing Systems	2017-08-15	Paper
Lower bounds for existential pebble games and \(k\)-consistency tests 2012 27th Annual IEEE Symposium on Logic in Computer Science	2017-05-16	Paper
Parameterized complexity of fixed variable logics	2017-04-25	Paper
Bounds for the quantifier depth in finite-variable logics: alternation hierarchy	2017-02-02	Paper
Limitations of algebraic approaches to graph isomorphism testing Automata, Languages, and Programming	2015-10-27	Paper
Bounds for the quantifier depth in finite-variable logics: alternation hierarchy ACM Transactions on Computational Logic	2015-09-17	Paper
Lower bounds for existential pebble games and \(k\)-consistency tests Logical Methods in Computer Science	2013-10-16	Paper
On the speed of constraint propagation and the time complexity of arc consistency testing Mathematical Foundations of Computer Science 2013	2013-09-20	Paper
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement Lecture Notes in Computer Science	2013-09-17	Paper

Research outcomes over time

This page was built for person: Christoph Berkholz