Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L. - Dieter van Melkebeek (CCC, 1996)

Sparse Hard Sets for P. - Dieter van Melkebeek; Mitsunori Ogihara (Advances in Algorithms, Languages, and Complexity, 1997)

A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). - Harry Buhrman; Dieter van Melkebeek; Kenneth W. Regan; D. Sivakumar; Martin Strauss 001 (STACS, 1998)

Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets. - Dieter van Melkebeek (J. Comput. Syst. Sci., 1998)

Hard Sets Are Hard to Find. - Harry Buhrman; Dieter van Melkebeek (J. Comput. Syst. Sci., 1999)

Randomness and Completeness in Computational Complexity - Dieter van Melkebeek (Springer, 2000)

Optimal Proof Systems and Sparse Sets. - Harry Buhrman; Stephen A. Fenner; Lance Fortnow; Dieter van Melkebeek (STACS, 2000)

Time-Space Tradeoffs for Nondeterministic Computation - Lance Fortnow; Dieter van Melkebeek (Electron. Colloquium Comput. Complex., 2000)

Separating Complexity Classes Using Autoreducibility. - Harry Buhrman; Lance Fortnow; Dieter van Melkebeek; Leen Torenvliet (SIAM J. Comput., 2000)

A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem. - Harry Buhrman; Dieter van Melkebeek; Kenneth W. Regan; D. Sivakumar; Martin Strauss 001 (SIAM J. Comput., 2000)

The zero-one law holds for BPP. - Dieter van Melkebeek (Theor. Comput. Sci., 2000)

Computational Depth. - Luis Antunes 002; Lance Fortnow; Dieter van Melkebeek (CCC, 2001)

The Computational Complexity Column Time-Space Lower Bounds for Satisfiability. - Dieter van Melkebeek (Bull. EATCS, 2001)

The Quantum Black-Box Complexity of Majority. - Thomas P. Hayes; Samuel Kutin; Dieter van Melkebeek (Algorithmica, 2002)

Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. - Adam R. Klivans; Dieter van Melkebeek (SIAM J. Comput., 2002)

Holographic Proofs and Derandomization. - Rahul Santhanam; Dieter van Melkebeek (CCC, 2003)

Language compression and pseudorandom generators. - Harry Buhrman; Troy Lee; Dieter van Melkebeek (Comput. Complex., 2005)

A Generic Time Hierarchy for Semantic Models With One Bit of Advice - Dieter van Melkebeek; Konstantin Pervyshev (Electron. Colloquium Comput. Complex., 2005)

Time-space lower bounds for satisfiability. - Lance Fortnow; Richard J. Lipton; Dieter van Melkebeek; Anastasios Viglas (J. ACM, 2005)

Holographic Proofs and Derandmization. - Dieter van Melkebeek; Rahul Santhanam (SIAM J. Comput., 2005)

A time lower bound for satisfiability. - Dieter van Melkebeek; Ran Raz (Theor. Comput. Sci., 2005)

06111 Executive Summary – Complexity of Boolean Functions. - Matthias Krause 001; Dieter van Melkebeek; Pavel Pudlák; Rüdiger Reischuk (Complexity of Boolean Functions, 2006)

06111 Abstracts Collection – Complexity of Boolean Functions. - Matthias Krause 001; Pavel Pudlák; Rüdiger Reischuk; Dieter van Melkebeek (Complexity of Boolean Functions, 2006)

Time-Space Tradeoff in Derandomizing Probabilistic Logspace. - Jin-yi Cai; Venkatesan T. Chakaravarthy; Dieter van Melkebeek (Theory Comput. Syst., 2006)

Power from Random Strings. - Eric Allender; Harry Buhrman; Michal Koucký 001; Dieter van Melkebeek; Detlef Ronneburger (SIAM J. Comput., 2006)

Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. - Scott Diehl; Dieter van Melkebeek (SIAM J. Comput., 2006)

Computational depth: Concept and applications. - Luis Antunes 002; Lance Fortnow; Dieter van Melkebeek; N. V. Vinodchandran (Theor. Comput. Sci., 2006)

A Generic Time Hierarchy with One Bit of Advice. - Dieter van Melkebeek; Konstantin Pervyshev (Comput. Complex., 2007)

A Survey of Lower Bounds for Satisfiability and Related Problems. - Dieter van Melkebeek (Electron. Colloquium Comput. Complex., 2007)

08381 Abstracts Collection - Computational Complexity of Discrete Problems. - Peter Bro Miltersen; Rüdiger Reischuk; Georg Schnitger; Dieter van Melkebeek (Computational Complexity of Discrete Problems, 2008)

08381 Executive Summary - Computational Complexity of Discrete Problems. - Peter Bro Miltersen; Rüdiger Reischuk; Georg Schnitger; Dieter van Melkebeek (Computational Complexity of Discrete Problems, 2008)

Space Hierarchy Results for Randomized Models. - Jeff Kinne; Dieter van Melkebeek (STACS, 2008)

A Quantum Time-Space Lower Bound for the Counting Hierarchy. - Dieter van Melkebeek; Thomas Watson 001 (Electron. Colloquium Comput. Complex., 2008)

Pseudorandom Generators and Typically-Correct Derandomization. - Jeff Kinne; Dieter van Melkebeek; Ronen Shaltiel (APPROX-RANDOM, 2009)

Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006). - Scott Aaronson; Sudipto Guha; Jon M. Kleinberg; Frank McSherry; Dieter van Melkebeek; Amit Sahai (SIAM J. Comput., 2009)

Space Hierarchy Results for Randomized and other Semantic Models. - Jeff Kinne; Dieter van Melkebeek (Comput. Complex., 2010)

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. - Scott Aaronson; Baris Aydinlioglu; Harry Buhrman; John M. Hitchcock; Dieter van Melkebeek (Electron. Colloquium Comput. Complex., 2010)

A note on circuit lower bounds from derandomization. - Scott Aaronson; Dieter van Melkebeek (Electron. Colloquium Comput. Complex., 2010)

Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. - Matthew Anderson; Dieter van Melkebeek; Ilya Volkovich (Electron. Colloquium Comput. Complex., 2010)

Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. - Dieter van Melkebeek; Holger Dell (Electron. Colloquium Comput. Complex., 2010)

Time-Space Efficient Simulations of Quantum Computations. - Dieter van Melkebeek; Thomas Watson 001 (Electron. Colloquium Comput. Complex., 2010)

Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates. - Matthew Anderson; Dieter van Melkebeek; Nicole Schweikardt; Luc Segoufin (ICALP (2), 2011)

Special Issue "Conference on Computational Complexity 2010" Guest Editor's Foreword. - Dieter van Melkebeek (Comput. Complex., 2011)

Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121). - Martin Grohe; Michal Koucký 001; Rüdiger Reischuk; Dieter van Melkebeek (Dagstuhl Reports, 2011)

An improved time-space lower bound for tautologies. - Scott Diehl; Dieter van Melkebeek; Ryan Williams 001 (J. Comb. Optim., 2011)

On Circuit Lower Bounds from Derandomization. - Scott Aaronson; Dieter van Melkebeek (Theory Comput., 2011)

Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games. - Baris Aydinlioglu; Dieter van Melkebeek (CCC, 2012)

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. - Jeff Kinne; Dieter van Melkebeek; Ronen Shaltiel (Comput. Complex., 2012)

Locality from Circuit Lower Bounds. - Matthew Anderson; Dieter van Melkebeek; Nicole Schweikardt; Luc Segoufin (SIAM J. Comput., 2012)

Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011). - Kousha Etessami; Dieter van Melkebeek; Seth Pettie; John Watrous; Salil P. Vadhan (SIAM J. Comput., 2012)

On derandomization and average-case complexity of monotone functions. - George Karakostas; Jeff Kinne; Dieter van Melkebeek (Theor. Comput. Sci., 2012)

Is Valiant-Vazirani's isolation probability improvable? - Holger Dell; Valentine Kabanets; Dieter van Melkebeek; Osamu Watanabe 001 (Comput. Complex., 2013)

Deterministic polynomial identity tests for multilinear bounded-read formulae. - Matthew Anderson; Dieter van Melkebeek; Ilya Volkovich (Comput. Complex., 2015)

Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games. - Baris Aydinlioglu; Dieter van Melkebeek (Comput. Complex., 2017)

Minimum Circuit Size, Graph Isomorphism, and Related Problems. - Eric Allender; Joshua A. Grochow; Dieter van Melkebeek; Cristopher Moore; Andrew Morgan (SIAM J. Comput., 2018)

Derandomizing Isolation in Space-Bounded Settings. - Dieter van Melkebeek; Gautam Prakriya (SIAM J. Comput., 2019)

Query Complexity of Inversion Minimization on Trees. - Ivan Hu; Andrew Morgan; Dieter van Melkebeek (Electron. Colloquium Comput. Complex., 2022)

Polynomial Identity Testing via Evaluation of Rational Functions. - Dieter van Melkebeek; Andrew Morgan (Electron. Colloquium Comput. Complex., 2022)

Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols. - Dieter van Melkebeek; Nicollas M. Sdroievski (FSTTCS, 2023)

Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols. - Nicollas M. Sdroievski; Dieter van Melkebeek (Electron. Colloquium Comput. Complex., 2023)

Polynomial Identity Testing via Evaluation of Rational Functions. - Ivan Hu; Dieter van Melkebeek; Andrew Morgan (Theory Comput., 2024)

Lower Bound Techniques in the Comparison-Query Model and Applications to Inversion Minimization. - Ivan Hu; Dieter van Melkebeek; Andrew Morgan (Theory Comput., 2024)

From Dynamic Programs to Greedy Algorithms. - Dieter van Melkebeek (CoRR, 2025)