| 2023 | SODA | Query Complexity of Inversion Minimization on Trees. | Ivan Hu, Dieter van Melkebeek, Andrew Morgan |
| 2011 | ICALP | Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates. | Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin |
| 2010 | STOC | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. | Holger Dell, Dieter van Melkebeek |
| 2009 | COCOON | An Improved Time-Space Lower Bound for Tautologies. | Scott Diehl, Dieter van Melkebeek, Ryan Williams |
| 2008 | STACS | Space Hierarchy Results for Randomized Models. | Jeff Kinne, Dieter van Melkebeek |
| 2005 | ICALP | Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. | Scott Diehl, Dieter van Melkebeek |
| 2004 | ICALP | A Time Lower Bound for Satisfiability. | Dieter van Melkebeek, Ran Raz |
| 2004 | STACS | Time-Space Tradeoff in Derandomizing Probabilistic Logspace. | Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek |
| 2002 | FOCS | Power from Random Strings. | Eric Allender, Harry Buhrman, Michal Kouck, Dieter van Melkebeek, Detlef Ronneburger |
| 2000 | STACS | Optimal Proof Systems and Sparse Sets. | Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek |
| 1999 | STOC | Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. | Adam R. Klivans, Dieter van Melkebeek |
| 1998 | STACS | A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). | Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss |