Jochen Messner

According to our database, Jochen Messner authored at least 15 papers between 1997 and 2015.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2015

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

2013

Exact Perfect Matching in Complete Graphs.

Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf

Electron. Colloquium Comput. Complex., 2013

2012

A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability.

Jochen Messner, Thomas Thierauf

Theor. Comput. Sci., 2012

2011

Planarizing Gadgets for Perfect Matching do not Exist.

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf

Electron. Colloquium Comput. Complex., 2011

2009

Nondeterministic functions and the existence of optimal proof systems.

Olaf Beyersdorff, Johannes Köbler, Jochen Messner

Theor. Comput. Sci., 2009

2004

On the complexity of resolution with bounded conjunctions.

Juan Luis Esteban, Nicola Galesi, Jochen Messner

Theor. Comput. Sci., 2004

2003

Optimal proof systems imply complete sets for promise classes.

Johannes Köbler, Jochen Messner, Jacobo Torán

Inf. Comput., 2003

2002

On the Structure of the Simulation Order of Proof Systems.

Jochen Messner

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

2001

On the simulation order of proof systems.

Jochen Messner

PhD thesis, 2001

2000

Is the Standard Proof System for SAT P-Optimal?

Johannes Köbler, Jochen Messner

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

1999

On Optimal Algorithms and Optimal Proof Systems.

Jochen Meßner

Proceedings of the STACS 99, 1999

"Good Enough" Testing of Nondeterministic Parallel Programs.

Dieter Kranzlmüller, Jochen Messner, Christian Schaubschläger

Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 1999

1998

Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets.

Johannes Köbler, Jochen Messner

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Optimal proof systems for Propositional Logic and complete sets

Jochen Meßner, Jacobo Torán

Electron. Colloquium Comput. Complex., 1997

Pattern Matching in Trace Monoids (Extended Abstract).

Jochen Meßner

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997