Dieter van Melkebeek

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