Instituts-Logo Logik in der Informatik
Prof. Dr. Nicole Schweikardt
Humboldt-Logo

Dr. Christoph Berkholz

Physical office:   Johann von Neumann-Haus
Haus 3 / 4. Etage, Raum 422
Rudower Chaussee 25
12489 Berlin (Adlershof)
Postal address:   Humboldt-Universität zu Berlin
Institut für Informatik
Unter den Linden 6
D-10099 Berlin
Phone: +49-30-2093 3079
Email: replace-by-last-name@informatik.hu-berlin.de
URL: www.informatik.hu-berlin.de/~berkhoch/

About

I am postdoctoral researcher at the Institute of Computer Science of the Humboldt University of Berlin within the Logic in Computer Science group led by Prof. Dr. Nicole Schweikardt.

Teaching

SoSe 2017 Vorlesung und Übung Einführung in die Beweiskomplexität
SoSe 2016 Übung Ausgewählte Kapitel der Logik
WS 2015/16 Seminar Aktuelle Themen in Logik und Komplexität
WS 2014/15 Übung Foundations of Data Science (RWTH Aachen)
Seminar Probabilistische Datenbanken (RWTH Aachen)
SoSe 2014 Seminar Aktuelle Themen der Theoretischen Informatik (RWTH Aachen)
Projektpraktikum Informatik-Praktikum für Mathematiker (RWTH Aachen)
WS 2013/14 Seminar Berechnungsmodelle für "Big Data" (RWTH Aachen)
SoSe 2013 Übung Theory of Constraint Satisfaction Problems (RWTH Aachen)
WS 2012/13 Seminar Logik und Komplexität (RWTH Aachen)
SoSe 2012 Seminar Logik und Komplexität
WS 2011/12 Übung Logik in der Informatik

Publications and Preprints

See also at dblp and arXiv.
The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs
Preprint: Electronic Colloquium on Computational Complexity (ECCC), Report No. 154 (2017).
 
Answering UCQs under updates and in the presence of integrity constraints
joint work with Jens Keppeler and Nicole Schweikardt
Preprint: CoRR, vol. abs/1709.10039, 2017.
 
Answering FO+MOD queries under updates on bounded degree databases
joint work with Jens Keppeler and Nicole Schweikardt
Preprint: CoRR, vol. abs/1702.08764, 2017.
Conference version: Proceedings of the 20th International Conference on Database Theory (ICDT'17), pp.8:1-8:18, 2017.
Journal version: Invited to ACM Transactions on Database Systems (TODS).
 
Answering Conjunctive Queries under Updates
joint work with Jens Keppeler and Nicole Schweikardt
Preprint: CoRR, vol. abs/1702.06370, 2017.
Conference version: Proceedings of the 36th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'17), pp.303-318, 2017.
Poster: The poster presented at PODS'17.
 
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
joint work with Martin Grohe
Preprint: CoRR, vol. abs/1607.04287, 2016.
Conference version: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), pp.327-339, 2017.
 
Supercritical Space-Width Trade-offs for Resolution
joint work with Jakob Nordström
Conference version: Proceedings of the 43nd International Colloquium on Automata, Languages and Programming (ICALP'16), pp.57:1-57:14, 2016.
Preprint: CoRR, vol. abs/1612.07162, 2016.
 
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
joint work with Jakob Nordström
Conference version: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), pp.267-276, 2016.
Preprint: CoRR, vol. abs/1608.08704, 2016.
 
Limitations of Algebraic Approaches to Graph Isomorphism Testing
joint work with Martin Grohe
Preprint: CoRR, vol. abs/1502.05912, 2015.
Conference version: Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP'15).
 
Parameterized Complexity of Fixed-Variable Logics
joint work with Michael Elberfeld
Conference version: Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'14).
 
The Propagation Depth of Local Consistency
Preprint: CoRR, vol. abs/1406.4679, 2014.
Conference version: Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming (CP'14), 2014.
 
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
joint work with Paul Bonsma and Martin Grohe
Journal version: Theory of Computing Systems (TOCS), Volume 60, Issue 4, pp. 581–614, 2017.
Preprint: CoRR, vol. abs/1509.08251, 2015.
Conference version: Proceedings of the 21st Annual European Symposium on Algorithms (ESA'13), Lecture Notes in Computer Science 8125, pp.145-156, 2013.
 
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy
joint work with Andreas Krebs and Oleg Verbitsky
Journal version: ACM Transactions on Computational Logic (TOCL), Volume 16, Issue 3, 2015.
Preprint: CoRR, vol. abs/1212.2747, 2013.
Conference version: Proceedings of the 22nd EACSL Annual Conference on Computer Science Logic (CSL'13), pp.61-80, 2013.
 
On the speed of constraint propagation and the time complexity of arc consistency testing
joint work with Oleg Verbitsky
Preprint: CoRR, vol. abs/1303.7077, 2012.
Conference version: Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS '13), Lecture Notes in Computer Science Volume 8087, pp.159-170, 2013.
Journal version: Journal of Computer and System Sciences (JCSS), Volume 91, pp.104-114, 2018.
 
On the Complexity of Finding Narrow Proofs
Preprint: CoRR, vol. abs/1204.0775, 2012.
Conference version: Proceedings of the 53th IEEE Symposium on Foundations of Computer Science (FOCS'12), pp.351-360, 2012.
 
Lower Bounds for Existential Pebble Games and k-Consistency Tests
Journal version: Logical Methods in Computer Science (LMCS), Volume 9, Issue 4, 2013.
Conference version: Proceedings of the 27th IEEE Symposium on Logic in Computer Science (LICS'12), pp.25-34, 2012.
 

Theses

Lower Bounds for Heuristic Algorithms
Dissertation: RWTH Aachen University, 2014.
Summary (in german): Untere Schranken für heuristische Algorithmen. In: Steffen Hölldobler et. al. (Hrsg.). Ausgezeichnete Informatikdissertationen 2014, pp.31-40, Lecture Notes in Informatics (LNI), Gesellschaft für Informatik, Bonn 2015.
 
Über die Schaltkreiskomplexität parametrisierter Probleme
Diploma thesis (in german): Humboldt-Universität zu Berlin, 2010.