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

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

2013

Exact Perfect Matching in Complete Graphs.

Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf

Electron. Colloquium Comput. Complex., 2013

2012

Planarizing Gadgets for Perfect Matching Do Not Exist.

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

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011

A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability.

Jochen Messner, Thomas Thierauf

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2009

Nondeterministic functions and the existence of optimal proof systems.

Olaf Beyersdorff, Johannes Köbler, Jochen Messner

Theor. Comput. Sci., 2009

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

On the Complexity of Resolution with Bounded Conjunctions.

Juan Luis Esteban, Nicola Galesi, Jochen Messner

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 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

Optimal Proof Systems for Propositional Logic and Complete Sets.

Jochen Meßner, Jacobo Torán

Proceedings of the STACS 98, 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

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