| 2015 | TIME | The Model Checking Fingerprints of CTL Operators. | Andreas Krebs, Arne Meier, Martin Mundhenk |
| 2012 | AiML | The Complexity of Monotone Hybrid Logics over Linear Frames and the Natural Numbers. | Stefan Gller, Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Felix Wei |
| 2011 | STACS | The model checking problem for propositional intuitionistic logic with one variable is AC^1-complete. | Martin Mundhenk, Felix Wei |
| 2011 | SAT | How to Apply SAT-Solving for the Equivalence Test of Monotone Normal Forms. | Martin Mundhenk, Robert Zeranski |
| 2009 | ALENEX | Experimental comparison of the two Fredman-Khachiyan-algorithms. | Matthias Hagen, Peter Horatschek, Martin Mundhenk |
| 2009 | MFCS | The Complexity of Satisfiability for Fragments of Hybrid Logic-Part I. | Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber, Felix Weiss |
| 2009 | TIME | Model Checking CTL is Almost Always Inherently Sequential. | Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer, Martin Mundhenk, Thomas Schneider |
| 2006 | MDM | SOGOS - A Distributed Meta Level Architecture for the Self-Organizing Grid of Services. | Clemens Beckstein, Peter Dittrich, Christian Erfurth, Dietmar Fey, Birgitta Knig-Ries, Martin Mundhenk, Harald Sack |
| 2005 | MFCS | Complexity of DNF and Isomorphism of Monotone Formulas. | Judy Goldsmith, Matthias Hagen, Martin Mundhenk |
| 2000 | STACS | Nondeterministic Instance Complexity and Hard-to-Prove Tautologies. | Vikraman Arvind, Johannes Kbler, Martin Mundhenk, Jacobo Torn |
| 1997 | GI | 33. Workshop "Komplexittstheorie, Datenstrukturen und Effiziente Algorithmen". | Christoph Meinel, Carsten Damm, Martin Mundhenk |
| 1997 | MFCS | NP-Hard Sets Have Many Hard Instances. | Martin Mundhenk |
| 1997 | MFCS | The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes. | Martin Mundhenk, Judy Goldsmith, Eric Allender |
| 1997 | UAI | The Complexity of Plan Existence and Evaluation in Probabilistic Domains. | Judy Goldsmith, Michael L. Littman, Martin Mundhenk |
| 1995 | LATIN | On Monotonous Oracle Machines. | Martin Mundhenk |
| 1994 | CIAC | On Self-Reducible Sets of Low Information Content. | Martin Mundhenk |
| 1993 | MFCS | Hausdorff Reductions to Sparse Sets and to Sets of High Information Content. | Vikraman Arvind, Johannes Kbler, Martin Mundhenk |
| 1992 | ICALP | Reductions to Sets of Low Information Content. | Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Kbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schning, Riccardo Silvestri, Thomas Thierauf |
| 1992 | ISAAC | Lowness and the Complexity of Sparse and Tally Descriptions. | Vikraman Arvind, Johannes Kbler, Martin Mundhenk |