Dieter van Melkebeek

According to our database, Dieter van Melkebeek authored at least 60 papers between 1996 and 2023.

Collaborative distances:

• Dijkstra number of two.
• Erdős number of three.

2023

Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols.

Nicollas M. Sdroievski, Dieter van Melkebeek

Electron. Colloquium Comput. Complex., 2023

Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols.

Dieter van Melkebeek, Nicollas M. Sdroievski

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

2022

Polynomial Identity Testing via Evaluation of Rational Functions.

Dieter van Melkebeek, Andrew Morgan

Electron. Colloquium Comput. Complex., 2022

Query Complexity of Inversion Minimization on Trees.

Ivan Hu, Andrew Morgan, Dieter van Melkebeek

Electron. Colloquium Comput. Complex., 2022

2017

Derandomizing Isolation in Space-Bounded Settings.

Dieter van Melkebeek, Gautam Prakriya

Electron. Colloquium Comput. Complex., 2017

Minimum Circuit Size, Graph Isomorphism, and Related Problems.

Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan

Electron. Colloquium Comput. Complex., 2017

Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games.

Baris Aydinlioglu, Dieter van Melkebeek

Comput. Complex., 2017

2015

Deterministic polynomial identity tests for multilinear bounded-read formulae.

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich

Comput. Complex., 2015

2014

Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses.

Holger Dell, Dieter van Melkebeek

J. ACM, 2014

2013

Is Valiant-Vazirani's isolation probability improvable?

Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe

Comput. Complex., 2013

2012

Time-Space Efficient Simulations of Quantum Computations.

Dieter van Melkebeek, Thomas Watson

Theory Comput., 2012

On derandomization and average-case complexity of monotone functions.

George Karakostas, Jeff Kinne, Dieter van Melkebeek

Theor. Comput. Sci., 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

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds.

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel

Comput. Complex., 2012

Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games.

Baris Aydinlioglu, Dieter van Melkebeek

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

On Circuit Lower Bounds from Derandomization.

Scott Aaronson, Dieter van Melkebeek

Theory Comput., 2011

An improved time-space lower bound for tautologies.

Scott Diehl, Dieter van Melkebeek, Ryan Williams

J. Comb. Optim., 2011

Locality from Circuit Lower Bounds.

Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin

Electron. Colloquium Comput. Complex., 2011

Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121).

Martin Grohe, Michal Koucký, Rüdiger Reischuk, Dieter van Melkebeek

Dagstuhl Reports, 2011

Special Issue "Conference on Computational Complexity 2010" Guest Editor's Foreword.

Dieter van Melkebeek

Comput. Complex., 2011

Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates.

Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae.

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2010

A note on circuit lower bounds from derandomization.

Scott Aaronson, Dieter van Melkebeek

Electron. Colloquium 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

Space Hierarchy Results for Randomized and other Semantic Models.

Jeff Kinne, Dieter van Melkebeek

Comput. Complex., 2010

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

Pseudorandom Generators and Typically-Correct Derandomization.

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel

Proceedings of the Approximation, 2009

2008

A Quantum Time-Space Lower Bound for the Counting Hierarchy.

Dieter van Melkebeek, Thomas Watson

Electron. Colloquium Comput. Complex., 2008

Space Hierarchy Results for Randomized Models.

Jeff Kinne, Dieter van Melkebeek

Proceedings of the STACS 2008, 2008

08381 Executive Summary - Computational Complexity of Discrete Problems.

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, Dieter van Melkebeek

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

08381 Abstracts Collection - Computational Complexity of Discrete Problems.

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, Dieter van Melkebeek

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

2007

A Survey of Lower Bounds for Satisfiability and Related Problems.

Dieter van Melkebeek

Electron. Colloquium Comput. Complex., 2007

A Generic Time Hierarchy with One Bit of Advice.

Dieter van Melkebeek, Konstantin Pervyshev

Comput. Complex., 2007

2006

Computational depth: Concept and applications.

Luis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran

Theor. Comput. Sci., 2006

Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines.

Scott Diehl, Dieter van Melkebeek

SIAM J. Comput., 2006

Time-Space Tradeoff in Derandomizing Probabilistic Logspace.

Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek

Theory Comput. Syst., 2006

06111 Abstracts Collection -- Complexity of Boolean Functions.

Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

06111 Executive Summary -- Complexity of Boolean Functions.

Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, Rüdiger Reischuk

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

2005

A time lower bound for satisfiability.

Dieter van Melkebeek, Ran Raz

Theor. Comput. Sci., 2005

Holographic Proofs and Derandmization.

Dieter van Melkebeek, Rahul Santhanam

SIAM J. Comput., 2005

Time-space lower bounds for satisfiability.

Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas

J. ACM, 2005

A Generic Time Hierarchy for Semantic Models With One Bit of Advice

Dieter van Melkebeek, Konstantin Pervyshev

Electron. Colloquium Comput. Complex., 2005

Language compression and pseudorandom generators.

Harry Buhrman, Troy Lee, Dieter van Melkebeek

Comput. Complex., 2005

2003

Holographic Proofs and Derandomization.

Rahul Santhanam, Dieter van Melkebeek

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Power from Random Strings

Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek

Electron. Colloquium Comput. Complex., 2002

The Quantum Black-Box Complexity of Majority.

Thomas P. Hayes, Samuel Kutin, Dieter van Melkebeek

Algorithmica, 2002

2001

The Computational Complexity Column Time-Space Lower Bounds for Satisfiability.

Dieter van Melkebeek

Bull. EATCS, 2001

Computational Depth.

Luis Antunes, Lance Fortnow, Dieter van Melkebeek

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

The zero-one law holds for BPP.

Dieter van Melkebeek

Theor. Comput. Sci., 2000

Separating Complexity Classes Using Autoreducibility.

Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet

SIAM J. Comput., 2000

Time-Space Tradeoffs for Nondeterministic Computation

Lance Fortnow, Dieter van Melkebeek

Electron. Colloquium Comput. Complex., 2000

Optimal Proof Systems and Sparse Sets.

Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek

Proceedings of the STACS 2000, 2000

Randomness and Completeness in Computational Complexity

Dieter van Melkebeek

Lecture Notes in Computer Science 1950, Springer, ISBN: 3-540-41492-4, 2000

1999

Hard Sets Are Hard to Find.

Harry Buhrman, Dieter van Melkebeek

J. Comput. Syst. Sci., 1999

1998

Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets.

Dieter van Melkebeek

J. Comput. Syst. Sci., 1998

Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

Adam R. Klivans, Dieter van Melkebeek

Electron. Colloquium Comput. Complex., 1998

A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem

Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, Martin Strauss, D. Sivakumar

Electron. Colloquium Comput. Complex., 1998

A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract).

Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss

Proceedings of the STACS 98, 1998

1997

Sparse Hard Sets for P.

Dieter van Melkebeek, Mitsunori Ogihara

Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

1996

Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L.

Dieter van Melkebeek

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996