Pattern Matching in Trace Monoids (Extended Abstract). - Jochen Meßner (STACS, 1997)

Optimal proof systems for Propositional Logic and complete sets - Jochen Meßner; Jacobo Torán (Electron. Colloquium Comput. Complex., 1997)

Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets. - Johannes Köbler; Jochen Messner (CCC, 1998)

"Good Enough" Testing of Nondeterministic Parallel Programs. - Dieter Kranzlmüller; Jochen Messner; Christian Schaubschläger (PDPTA, 1999)

On Optimal Algorithms and Optimal Proof Systems. - Jochen Meßner (STACS, 1999)

Is the Standard Proof System for SAT P-Optimal? - Johannes Köbler; Jochen Messner (FSTTCS, 2000)

On the simulation order of proof systems. - Jochen Messner (2001)

On the Structure of the Simulation Order of Proof Systems. - Jochen Messner (MFCS, 2002)

Optimal proof systems imply complete sets for promise classes. - Johannes Köbler; Jochen Messner; Jacobo Torán (Inf. Comput., 2003)

On the complexity of resolution with bounded conjunctions. - Juan Luis Esteban; Nicola Galesi; Jochen Messner (Theor. Comput. Sci., 2004)

Nondeterministic functions and the existence of optimal proof systems. - Olaf Beyersdorff; Johannes Köbler; Jochen Messner (Theor. Comput. Sci., 2009)

Planarizing Gadgets for Perfect Matching do not Exist. - Rohit Gurjar; Arpita Korwar; Jochen Messner; Simon Straub; Thomas Thierauf (Electron. Colloquium Comput. Complex., 2011)

A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability. - Jochen Messner; Thomas Thierauf (Theor. Comput. Sci., 2012)

Exact Perfect Matching in Complete Graphs. - Rohit Gurjar; Arpita Korwar; Jochen Messner; Thomas Thierauf (Electron. Colloquium Comput. Complex., 2013)

Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. - Stephen A. Fenner; Daniel Grier; Jochen Messner; Luke Schaeffer; Thomas Thierauf (Electron. Colloquium Comput. Complex., 2015)