Dieter van Melkebeek

Publication Activity (10 Years)

Years Active: 1996-2023
Publications (10 Years): 17

Top Topics

Related Problems

Graph Isomorphism

Query Complexity

Top Venues

Electron. Colloquium Comput. Complex.

Comput. Complex.

Publications

Ivan Hu, Dieter van Melkebeek, Andrew Morgan
Query Complexity of Inversion Minimization on Trees. SODA (2023)
Dieter van Melkebeek, Nicollas M. Sdroievski
Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols. CCC (2023)
Nicollas M. Sdroievski, Dieter van Melkebeek
Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols. Electron. Colloquium Comput. Complex. (2023)
Dieter van Melkebeek, Nicollas M. Sdroievski
Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols. FSTTCS (2023)
Dieter van Melkebeek, Andrew Morgan
Polynomial Identity Testing via Evaluation of Rational Functions. CoRR (2022)
Ivan Hu, Dieter van Melkebeek, Andrew Morgan
Query Complexity of Inversion Minimization on Trees. CoRR (2022)
Ivan Hu, Andrew Morgan, Dieter van Melkebeek
Query Complexity of Inversion Minimization on Trees. Electron. Colloquium Comput. Complex. (2022)
Dieter van Melkebeek, Andrew Morgan
Polynomial Identity Testing via Evaluation of Rational Functions. ITCS (2022)
Dieter van Melkebeek, Andrew Morgan
Polynomial Identity Testing via Evaluation of Rational Functions. Electron. Colloquium Comput. Complex. (2022)
Dieter van Melkebeek, Gautam Prakriya
Derandomizing Isolation in Space-Bounded Settings. SIAM J. Comput. 48 (3) (2019)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. SIAM J. Comput. 47 (4) (2018)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. ITCS (2018)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. Electron. Colloquium Comput. Complex. 24 (2017)
Baris Aydinlioglu, Dieter van Melkebeek
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games. Comput. Complex. 26 (1) (2017)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. CoRR (2017)
Dieter van Melkebeek, Gautam Prakriya
Derandomizing Isolation in Space-Bounded Settings. Electron. Colloquium Comput. Complex. 24 (2017)
Dieter van Melkebeek, Gautam Prakriya
Derandomizing Isolation in Space-Bounded Settings. Computational Complexity Conference (2017)
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
Deterministic polynomial identity tests for multilinear bounded-read formulae. Comput. Complex. 24 (4) (2015)
Holger Dell, Dieter van Melkebeek
Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses. J. ACM 61 (4) (2014)
Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe
Is Valiant-Vazirani's isolation probability improvable? Comput. Complex. 22 (2) (2013)
Baris Aydinlioglu, Dieter van Melkebeek
Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. Electron. Colloquium Comput. Complex. 19 (2012)
George Karakostas, Jeff Kinne, Dieter van Melkebeek
On derandomization and average-case complexity of monotone functions. Theor. Comput. Sci. 434 (2012)
Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe
Is Valiant-Vazirani's Isolation Probability Improvable? Computational Complexity Conference (2012)
Kousha Etessami, Dieter van Melkebeek, Seth Pettie, John Watrous, Salil P. Vadhan
Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011). SIAM J. Comput. 41 (5) (2012)
Baris Aydinlioglu, Dieter van Melkebeek
Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games. Computational Complexity Conference (2012)
Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin
Locality from Circuit Lower Bounds. SIAM J. Comput. 41 (6) (2012)
Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel
Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. Comput. Complex. 21 (1) (2012)
Dieter van Melkebeek, Thomas Watson
Time-Space Efficient Simulations of Quantum Computations. Theory Comput. 8 (1) (2012)
Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin
Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates. ICALP (2) (2011)
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. Computational Complexity Conference (2011)
Scott Aaronson, Dieter van Melkebeek
On Circuit Lower Bounds from Derandomization. Theory Comput. 7 (1) (2011)
Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin
Locality from Circuit Lower Bounds. Electron. Colloquium Comput. Complex. 18 (2011)
Scott Diehl, Dieter van Melkebeek, Ryan Williams
An improved time-space lower bound for tautologies. J. Comb. Optim. 22 (3) (2011)
Dieter van Melkebeek
Special Issue "Conference on Computational Complexity 2010" Guest Editor's Foreword. Comput. Complex. 20 (2) (2011)
Martin Grohe, Michal Koucký, Rüdiger Reischuk, Dieter van Melkebeek
Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121). Dagstuhl Reports 1 (3) (2011)
Jeff Kinne, Dieter van Melkebeek
Space Hierarchy Results for Randomized and other Semantic Models. Comput. Complex. 19 (3) (2010)
Dieter van Melkebeek, Thomas Watson
Time-Space Efficient Simulations of Quantum Computations. Electron. Colloquium Comput. Complex. 17 (2010)
Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel
Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. Electron. Colloquium Comput. Complex. 17 (2010)
Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, Dieter van Melkebeek
A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. Electron. Colloquium Comput. Complex. 17 (2010)
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. Electron. Colloquium Comput. Complex. 17 (2010)
Dieter van Melkebeek, Holger Dell
Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. Electron. Colloquium Comput. Complex. 17 (2010)
Holger Dell, Dieter van Melkebeek
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. STOC (2010)
Scott Aaronson, Dieter van Melkebeek
A note on circuit lower bounds from derandomization. Electron. Colloquium Comput. Complex. 17 (2010)
Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel
Pseudorandom Generators and Typically-Correct Derandomization. APPROX-RANDOM (2009)
Holger Dell, Dieter van Melkebeek
Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. Parameterized complexity and approximation algorithms (2009)
Scott Aaronson, Sudipto Guha, Jon M. Kleinberg, Frank McSherry, Dieter van Melkebeek, Amit Sahai
Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006). SIAM J. Comput. 39 (1) (2009)
Scott Diehl, Dieter van Melkebeek, Ryan Williams
An Improved Time-Space Lower Bound for Tautologies. COCOON (2009)
Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, Dieter van Melkebeek
08381 Executive Summary - Computational Complexity of Discrete Problems. Computational Complexity of Discrete Problems (2008)
Dieter van Melkebeek, Thomas Watson
A Quantum Time-Space Lower Bound for the Counting Hierarchy. Electron. Colloquium Comput. Complex. 15 (017) (2008)
Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, Dieter van Melkebeek
08381 Abstracts Collection - Computational Complexity of Discrete Problems. Computational Complexity of Discrete Problems (2008)
Jeff Kinne, Dieter van Melkebeek
Space Hierarchy Results for Randomized Models. STACS (2008)
Dieter van Melkebeek
A Survey of Lower Bounds for Satisfiability and Related Problems. Electron. Colloquium Comput. Complex. 14 (099) (2007)
Jeff Kinne, Dieter van Melkebeek
Space Hierarchy Results for Randomized and Other Semantic Models. Electron. Colloquium Comput. Complex. 14 (134) (2007)
Dieter van Melkebeek, Konstantin Pervyshev
A Generic Time Hierarchy with One Bit of Advice. Comput. Complex. 16 (2) (2007)
Dieter van Melkebeek, Konstantin Pervyshev
A Generic Time Hierarchy for Semantic Models With One Bit of Advice. Complexity of Boolean Functions (2006)
Dieter van Melkebeek
A Survey of Lower Bounds for Satisfiability and Related Problems. Found. Trends Theor. Comput. Sci. 2 (3) (2006)
Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek
Time-Space Tradeoff in Derandomizing Probabilistic Logspace. Theory Comput. Syst. 39 (1) (2006)
Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek
06111 Abstracts Collection -- Complexity of Boolean Functions. Complexity of Boolean Functions (2006)
Luis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran
Computational depth: Concept and applications. Theor. Comput. Sci. 354 (3) (2006)
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger
Power from Random Strings. SIAM J. Comput. 35 (6) (2006)
Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, Rüdiger Reischuk
06111 Executive Summary -- Complexity of Boolean Functions. Complexity of Boolean Functions (2006)
Dieter van Melkebeek, Konstantin Pervyshev
A Generic Time Hierarchy for Semantic Models with One Bit of Advice. Computational Complexity Conference (2006)
Scott Diehl, Dieter van Melkebeek
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. SIAM J. Comput. 36 (3) (2006)
Scott Diehl, Dieter van Melkebeek
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. Complexity of Boolean Functions (2006)
Scott Diehl, Dieter van Melkebeek
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. ICALP (2005)
Dieter van Melkebeek, Konstantin Pervyshev
A Generic Time Hierarchy for Semantic Models With One Bit of Advice Electron. Colloquium Comput. Complex. (111) (2005)
Dieter van Melkebeek, Rahul Santhanam
Holographic Proofs and Derandmization. SIAM J. Comput. 35 (1) (2005)
Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas
Time-space lower bounds for satisfiability. J. ACM 52 (6) (2005)
Harry Buhrman, Troy Lee, Dieter van Melkebeek
Language compression and pseudorandom generators. Comput. Complex. 14 (3) (2005)
Dieter van Melkebeek, Ran Raz
A time lower bound for satisfiability. Theor. Comput. Sci. 348 (2-3) (2005)
Troy Lee, Dieter van Melkebeek, Harry Buhrman
Language Compression and Pseudorandom Generators Electron. Colloquium Comput. Complex. (002) (2004)
Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek
Time-Space Tradeoff in Derandomizing Probabilistic Logspace. STACS (2004)
Harry Buhrman, Troy Lee, Dieter van Melkebeek
Language Compression and Pseudorandom Generators. Computational Complexity Conference (2004)
Dieter van Melkebeek, Ran Raz
A Time Lower Bound for Satisfiability. ICALP (2004)
Rahul Santhanam, Dieter van Melkebeek
Holographic Proofs and Derandomization. Computational Complexity Conference (2003)
Thomas P. Hayes, Samuel Kutin, Dieter van Melkebeek
The Quantum Black-Box Complexity of Majority. Algorithmica 34 (4) (2002)
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger
Power from Random Strings. FOCS (2002)
Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek
Power from Random Strings Electron. Colloquium Comput. Complex. (028) (2002)
Adam R. Klivans, Dieter van Melkebeek
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. SIAM J. Comput. 31 (5) (2002)
Luis Antunes, Lance Fortnow, Dieter van Melkebeek
Computational Depth. Computational Complexity Conference (2001)
Dieter van Melkebeek
The Computational Complexity Column Time-Space Lower Bounds for Satisfiability. Bull. EATCS 73 (2001)
Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet
Separating Complexity Classes Using Autoreducibility. SIAM J. Comput. 29 (5) (2000)
Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem. SIAM J. Comput. 30 (2) (2000)
Dieter van Melkebeek
The zero-one law holds for BPP. Theor. Comput. Sci. 244 (1-2) (2000)
Lance Fortnow, Dieter van Melkebeek
Time-Space Tradeoffs for Nondeterministic Computation. Computational Complexity Conference (2000)
Lance Fortnow, Dieter van Melkebeek
Time-Space Tradeoffs for Nondeterministic Computation Electron. Colloquium Comput. Complex. 7 (28) (2000)
Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek
Optimal Proof Systems and Sparse Sets. STACS (2000)
Adam R. Klivans, Dieter van Melkebeek
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. STOC (1999)
Harry Buhrman, Dieter van Melkebeek
Hard Sets Are Hard to Find. J. Comput. Syst. Sci. 59 (2) (1999)
Dieter van Melkebeek
Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets. J. Comput. Syst. Sci. 57 (2) (1998)
Adam R. Klivans, Dieter van Melkebeek
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. Electron. Colloquium Comput. Complex. 5 (75) (1998)
Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, Martin Strauss, D. Sivakumar
A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem Electron. Colloquium Comput. Complex. 5 (58) (1998)
Harry Buhrman, Dieter van Melkebeek
Hard Sets are Hard to Find. Computational Complexity Conference (1998)
Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). STACS (1998)
Dieter van Melkebeek, Mitsunori Ogihara
Sparse Hard Sets for P. Advances in Algorithms, Languages, and Complexity (1997)
Dieter van Melkebeek
Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L. Computational Complexity Conference (1996)