Christoph Berkholz

Christoph Berkholz

Contact

Mail RWTH Aachen, Lehrstuhl für Informatik 7, 52056 Aachen
Office Room 4117b, Building E1, Ahornstr. 55, 52074 Aachen
Phone +49 (241) 80 21708
Fax +49 (241) 80 22215
Email berkholz(at)informatik.rwth-aachen.de
Office Hours By appointment

I am graduate student in the DFG project "Schaltkreiskomplexität, parametrische Komplexität und logische Definierbarkeit". My advisor is Martin Grohe.

Research Interests

Logic, Parameterized Complexity, Circuit Complexity, Proof Complexity

Publications

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.

Teaching

Winter Term 2013/14
Seminar Computation Models for "Big Data"
Summer Term 2013
Exercise classes for the Lecture Theory of Constraint Satisfaction Problems
Winter Term 2012/2013
Seminar Logik und Komplexität