Christoph Berkholz

Christoph Berkholz

Kontakt

Anschrift RWTH Aachen, Lehrstuhl für Informatik 7, 52056 Aachen
Büro Raum 4117b, Gebäude E1, 1. Etage, Ahornstr. 55, 52074 Aachen
Telefon +49 (241) 80 21708
Telefax +49 (241) 80 22215
Email berkholz(at)informatik.rwth-aachen.de
Sprechstunde Nach Vereinbarung

Ich bin Doktorand von Martin Grohe und Mitarbeiter im DFG-Projekt "Schaltkreiskomplexität, parametrische Komplexität und logische Definierbarkeit".

Forschungsinteressen

Logik, parametrische Komplexität, Schaltkreiskomplexität, Beweiskomplexität

Publikationen

Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
joint work with Paul Bonsma and Martin Grohe
Preprint: Available upon request.
Conference version: Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013), 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
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.
 
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.
 
Über die Schaltkreiskomplexität parametrisierter Probleme
Diplomarbeit: Humboldt-Universität zu Berlin, 2010.

Lehre

Wintersemester 2013/14
Seminar Berechnungsmodelle für "Big Data"
Sommersemester 2013
Übung zur Vorlesung Theory of Constraint Satisfaction Problems
Wintersemester 2012/2013
Seminar über Logik und Komplexität