Jochen Messner

19 papers A* 1A 1B 3Misc 2Journal 10Unranked 1
YearRankTypeTitle / Venue / Authors
2017 J jnl
Exact Perfect Matching in Complete Graphs.
ACM Trans. Comput. Theory
Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf
2016 J jnl
Planarizing Gadgets for Perfect Matching Do Not Exist.
ACM Trans. Comput. Theory
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
2015 B conf
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games.
ISAAC
Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
2015 J jnl
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games.
Electron. Colloquium Comput. Complex.
Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
2013 J jnl
Exact Perfect Matching in Complete Graphs.
Electron. Colloquium Comput. Complex.
Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf
2012 J jnl
A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability.
Theor. Comput. Sci.
Jochen Messner, Thomas Thierauf
2012 B conf
Planarizing Gadgets for Perfect Matching Do Not Exist.
MFCS
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
2011 Misc conf
A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability.
COCOON
Jochen Messner, Thomas Thierauf
2011 J jnl
A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability.
Electron. Colloquium Comput. Complex.
Jochen Messner, Thomas Thierauf
2011 J jnl
Planarizing Gadgets for Perfect Matching do not Exist.
Electron. Colloquium Comput. Complex.
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
2009 J jnl
Nondeterministic functions and the existence of optimal proof systems.
Theor. Comput. Sci.
Olaf Beyersdorff, Johannes Köbler, Jochen Messner
2004 J jnl
On the complexity of resolution with bounded conjunctions.
Theor. Comput. Sci.
Juan Luis Esteban, Nicola Galesi, Jochen Messner
2003 J jnl
Optimal proof systems imply complete sets for promise classes.
Inf. Comput.
Johannes Köbler, Jochen Messner, Jacobo Torán
2002 A* conf
On the Complexity of Resolution with Bounded Conjunctions.
ICALP
Juan Luis Esteban, Nicola Galesi, Jochen Messner
2002 B conf
On the Structure of the Simulation Order of Proof Systems.
MFCS
Jochen Messner
2001 — —
On the simulation order of proof systems.
Jochen Messner
2000 — conf
Is the Standard Proof System for SAT P-Optimal?
FSTTCS
Johannes Köbler, Jochen Messner
1999 Misc conf
"Good Enough" Testing of Nondeterministic Parallel Programs.
PDPTA
Dieter Kranzlmüller, Jochen Messner, Christian Schaubschläger
1998 A conf
Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets.
CCC
Johannes Köbler, Jochen Messner