Dieter van Melkebeek

Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe: Is Valiant-Vazirani's isolation probability improvable? Computational Complexity 22(2): 345-383 (2013)

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel: Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. Computational Complexity 21(1): 3-61 (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): 1233-1234 (2012)

Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin: Locality from Circuit Lower Bounds. SIAM J. Comput. 41(6): 1481-1523 (2012)

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

Dieter van Melkebeek, Thomas Watson: Time-Space Efficient Simulations of Quantum Computations. Theory of Computing 8(1): 1-51 (2012)

Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe: Is Valiant-Vazirani's Isolation Probability Improvable? IEEE Conference on Computational Complexity 2012: 10-20

Baris Aydinlioglu, Dieter van Melkebeek: Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games. IEEE Conference on Computational Complexity 2012: 269-279

Baris Aydinlioglu, Dieter van Melkebeek: Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. Electronic Colloquium on Computational Complexity (ECCC) 19: 80 (2012)

Dieter van Melkebeek: Special Issue "Conference on Computational Complexity 2010" Guest Editor's Foreword. Computational Complexity 20(2): 173-175 (2011)

Scott Diehl, Dieter van Melkebeek, Ryan Williams: An improved time-space lower bound for tautologies. J. Comb. Optim. 22(3): 325-338 (2011)

Scott Aaronson, Dieter van Melkebeek: On Circuit Lower Bounds from Derandomization. Theory of Computing 7(1): 177-184 (2011)

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich: Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. IEEE Conference on Computational Complexity 2011: 273-282

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: 368-379

Martin Grohe, Michal Koucký, Rüdiger Reischuk, Dieter van Melkebeek: Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121). Dagstuhl Reports 1(3): 42-66 (2011)

Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin: Locality from Circuit Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC) 18: 158 (2011)

Jeff Kinne, Dieter van Melkebeek: Space Hierarchy Results for Randomized and other Semantic Models. Computational Complexity 19(3): 423-475 (2010)

Holger Dell, Dieter van Melkebeek: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. STOC 2010: 251-260

Dieter van Melkebeek, Holger Dell: Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. Electronic Colloquium on Computational Complexity (ECCC) 17: 38 (2010)

Scott Aaronson, Dieter van Melkebeek: A note on circuit lower bounds from derandomization. Electronic Colloquium on Computational Complexity (ECCC) 17: 105 (2010)

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel: Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC) 17: 129 (2010)

Dieter van Melkebeek, Thomas Watson: Time-Space Efficient Simulations of Quantum Computations. Electronic Colloquium on Computational Complexity (ECCC) 17: 147 (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. Electronic Colloquium on Computational Complexity (ECCC) 17: 174 (2010)

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich: Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. Electronic Colloquium on Computational Complexity (ECCC) 17: 188 (2010)

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)

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel: Pseudorandom Generators and Typically-Correct Derandomization. APPROX-RANDOM 2009: 574-587

Scott Diehl, Dieter van Melkebeek, Ryan Williams: An Improved Time-Space Lower Bound for Tautologies. COCOON 2009: 429-438

Jeff Kinne, Dieter van Melkebeek: Space Hierarchy Results for Randomized Models. STACS 2008: 433-444

Dieter van Melkebeek, Thomas Watson: A Quantum Time-Space Lower Bound for the Counting Hierarchy. Electronic Colloquium on Computational Complexity (ECCC) 15(017) (2008)

Dieter van Melkebeek, Konstantin Pervyshev: A Generic Time Hierarchy with One Bit of Advice. Computational Complexity 16(2): 139-179 (2007)

Dieter van Melkebeek: A Survey of Lower Bounds for Satisfiability and Related Problems. Electronic Colloquium on Computational Complexity (ECCC) 14(099) (2007)

Jeff Kinne, Dieter van Melkebeek: Space Hierarchy Results for Randomized and Other Semantic Models. Electronic Colloquium on Computational Complexity (ECCC) 14(134) (2007)

Dieter van Melkebeek: A Survey of Lower Bounds for Satisfiability and Related Problems. Foundations and Trends in Theoretical Computer Science 2(3): 197-303 (2006)

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

Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. SIAM J. Comput. 35(6): 1467-1493 (2006)

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

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

Dieter van Melkebeek, Konstantin Pervyshev: A Generic Time Hierarchy for Semantic Models with One Bit of Advice. IEEE Conference on Computational Complexity 2006: 129-144

Scott Diehl, Dieter van Melkebeek: Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. Complexity of Boolean Functions 2006

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

Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek: 06111 Abstracts Collection -- 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. Complexity of Boolean Functions 2006

Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek (Eds.): Complexity of Boolean Functions, 12.03. - 17.03.2006. Dagstuhl Seminar Proceedings 06111, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2006

Harry Buhrman, Troy Lee, Dieter van Melkebeek: Language compression and pseudorandom generators. Computational Complexity 14(3): 228-255 (2005)

Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas: Time-space lower bounds for satisfiability. J. ACM 52(6): 835-865 (2005)

Dieter van Melkebeek, Rahul Santhanam: Holographic Proofs and Derandmization. SIAM J. Comput. 35(1): 59-90 (2005)

Dieter van Melkebeek, Ran Raz: A time lower bound for satisfiability. Theor. Comput. Sci. 348(2-3): 311-320 (2005)

Scott Diehl, Dieter van Melkebeek: Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. ICALP 2005: 982-993

Dieter van Melkebeek, Konstantin Pervyshev: A Generic Time Hierarchy for Semantic Models With One Bit of Advice. Electronic Colloquium on Computational Complexity (ECCC)(111) (2005)

Harry Buhrman, Troy Lee, Dieter van Melkebeek: Language Compression and Pseudorandom Generators. IEEE Conference on Computational Complexity 2004: 15-28

Dieter van Melkebeek, Ran Raz: A Time Lower Bound for Satisfiability. ICALP 2004: 971-982

Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek: Time-Space Tradeoff in Derandomizing Probabilistic Logspace. STACS 2004: 571-583

Troy Lee, Dieter van Melkebeek, Harry Buhrman: Language Compression and Pseudorandom Generators. Electronic Colloquium on Computational Complexity (ECCC)(002) (2004)

Rahul Santhanam, Dieter van Melkebeek: Holographic Proofs and Derandomization. IEEE Conference on Computational Complexity 2003: 269-283

Thomas P. Hayes, Samuel Kutin, Dieter van Melkebeek: The Quantum Black-Box Complexity of Majority. Algorithmica 34(4): 480-501 (2002)

Adam Klivans, Dieter van Melkebeek: Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. SIAM J. Comput. 31(5): 1501-1526 (2002)

Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. FOCS 2002: 669-678

Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek: Power from Random Strings. Electronic Colloquium on Computational Complexity (ECCC)(028) (2002)

Dieter van Melkebeek: The Computational Complexity Column Time-Space Lower Bounds for Satisfiability. Bulletin of the EATCS 73: 57-77 (2001)

Luis Antunes, Lance Fortnow, Dieter van Melkebeek: Computational Depth. IEEE Conference on Computational Complexity 2001: 266-273

Dieter van Melkebeek: Randomness and Completeness in Computational Complexity. Lecture Notes in Computer Science 1950, Springer 2000, isbn 3-540-41492-4

Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet: Separating Complexity Classes Using Autoreducibility. SIAM J. Comput. 29(5): 1497-1520 (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): 576-601 (2000)

Dieter van Melkebeek: The zero-one law holds for BPP. Theor. Comput. Sci. 244(1-2): 283-288 (2000)

Lance Fortnow, Dieter van Melkebeek: Time-Space Tradeoffs for Nondeterministic Computation. IEEE Conference on Computational Complexity 2000: 2-13

Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek: Optimal Proof Systems and Sparse Sets. STACS 2000: 407-418

Lance Fortnow, Dieter van Melkebeek: Time-Space Tradeoffs for Nondeterministic Computation. Electronic Colloquium on Computational Complexity (ECCC) 7(28) (2000)

Harry Buhrman, Dieter van Melkebeek: Hard Sets Are Hard to Find. J. Comput. Syst. Sci. 59(2): 327-345 (1999)

Adam Klivans, Dieter van Melkebeek: Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. STOC 1999: 659-667

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

Harry Buhrman, Dieter van Melkebeek: Hard Sets are Hard to Find. IEEE Conference on Computational Complexity 1998: 170-181

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: 161-171

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. Electronic Colloquium on Computational Complexity (ECCC) 5(58) (1998)

Adam Klivans, Dieter van Melkebeek: Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. Electronic Colloquium on Computational Complexity (ECCC) 5(75) (1998)

Dieter van Melkebeek, Mitsunori Ogihara: Sparse Hard Sets for P. Advances in Algorithms, Languages, and Complexity 1997: 191-208

Dieter van Melkebeek: Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L. IEEE Conference on Computational Complexity 1996: 88-96