Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Dieter van Melkebeek
2010 – today
- 2013
[j29]Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe: Is Valiant-Vazirani's isolation probability improvable? Computational Complexity 22(2): 345-383 (2013)- 2012
- [j28]Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel: Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. Computational Complexity 21(1): 3-61 (2012)
- [j27]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)
- [j26]Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin: Locality from Circuit Lower Bounds. SIAM J. Comput. 41(6): 1481-1523 (2012)
- [j25]George Karakostas, Jeff Kinne, Dieter van Melkebeek: On derandomization and average-case complexity of monotone functions. Theor. Comput. Sci. 434: 35-44 (2012)
- [j24]Dieter van Melkebeek, Thomas Watson: Time-Space Efficient Simulations of Quantum Computations. Theory of Computing 8(1): 1-51 (2012)
- [c27]Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe: Is Valiant-Vazirani's Isolation Probability Improvable? IEEE Conference on Computational Complexity 2012: 10-20
- [c26]Baris Aydinlioglu, Dieter van Melkebeek: Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games. IEEE Conference on Computational Complexity 2012: 269-279
- [i18]Baris Aydinlioglu, Dieter van Melkebeek: Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. Electronic Colloquium on Computational Complexity (ECCC) 19: 80 (2012)
- 2011
- [j23]Dieter van Melkebeek: Special Issue "Conference on Computational Complexity 2010" Guest Editor's Foreword. Computational Complexity 20(2): 173-175 (2011)
- [j22]Scott Diehl, Dieter van Melkebeek, Ryan Williams: An improved time-space lower bound for tautologies. J. Comb. Optim. 22(3): 325-338 (2011)
- [j21]Scott Aaronson, Dieter van Melkebeek: On Circuit Lower Bounds from Derandomization. Theory of Computing 7(1): 177-184 (2011)
- [c25]Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich: Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. IEEE Conference on Computational Complexity 2011: 273-282
- [c24]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
- [i17]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)
- [i16]Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin: Locality from Circuit Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC) 18: 158 (2011)
- 2010
- [j20]Jeff Kinne, Dieter van Melkebeek: Space Hierarchy Results for Randomized and other Semantic Models. Computational Complexity 19(3): 423-475 (2010)
- [c23]Holger Dell, Dieter van Melkebeek: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. STOC 2010: 251-260
- [i15]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)
- [i14]Scott Aaronson, Dieter van Melkebeek: A note on circuit lower bounds from derandomization. Electronic Colloquium on Computational Complexity (ECCC) 17: 105 (2010)
- [i13]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)
- [i12]Dieter van Melkebeek, Thomas Watson: Time-Space Efficient Simulations of Quantum Computations. Electronic Colloquium on Computational Complexity (ECCC) 17: 147 (2010)
- [i11]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)
- [i10]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)
2000 – 2009
- 2009
- [j19]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)
- [c22]Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel: Pseudorandom Generators and Typically-Correct Derandomization. APPROX-RANDOM 2009: 574-587
- [c21]Scott Diehl, Dieter van Melkebeek, Ryan Williams: An Improved Time-Space Lower Bound for Tautologies. COCOON 2009: 429-438
- 2008
- [c20]Jeff Kinne, Dieter van Melkebeek: Space Hierarchy Results for Randomized Models. STACS 2008: 433-444
- [i9]Dieter van Melkebeek, Thomas Watson: A Quantum Time-Space Lower Bound for the Counting Hierarchy. Electronic Colloquium on Computational Complexity (ECCC) 15(017) (2008)
- 2007
- [j18]Dieter van Melkebeek, Konstantin Pervyshev: A Generic Time Hierarchy with One Bit of Advice. Computational Complexity 16(2): 139-179 (2007)
- [i8]Dieter van Melkebeek: A Survey of Lower Bounds for Satisfiability and Related Problems. Electronic Colloquium on Computational Complexity (ECCC) 14(099) (2007)
- [i7]Jeff Kinne, Dieter van Melkebeek: Space Hierarchy Results for Randomized and Other Semantic Models. Electronic Colloquium on Computational Complexity (ECCC) 14(134) (2007)
- 2006
- [j17]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)
- [j16]Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek: Time-Space Tradeoff in Derandomizing Probabilistic Logspace. Theory Comput. Syst. 39(1): 189-208 (2006)
- [j15]Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. SIAM J. Comput. 35(6): 1467-1493 (2006)
- [j14]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)
- [j13]Luis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran: Computational depth: Concept and applications. Theor. Comput. Sci. 354(3): 391-404 (2006)
- [c19]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
- [c18]Scott Diehl, Dieter van Melkebeek: Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. Complexity of Boolean Functions 2006
- [c17]Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, Rüdiger Reischuk: 06111 Executive Summary -- Complexity of Boolean Functions. Complexity of Boolean Functions 2006
- [c16]Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek: 06111 Abstracts Collection -- Complexity of Boolean Functions. Complexity of Boolean Functions 2006
- [c15]Dieter van Melkebeek, Konstantin Pervyshev: A Generic Time Hierarchy for Semantic Models With One Bit of Advice. Complexity of Boolean Functions 2006
- [e1]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
- 2005
- [j12]Harry Buhrman, Troy Lee, Dieter van Melkebeek: Language compression and pseudorandom generators. Computational Complexity 14(3): 228-255 (2005)
- [j11]Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas: Time-space lower bounds for satisfiability. J. ACM 52(6): 835-865 (2005)
- [j10]Dieter van Melkebeek, Rahul Santhanam: Holographic Proofs and Derandmization. SIAM J. Comput. 35(1): 59-90 (2005)
- [j9]Dieter van Melkebeek, Ran Raz: A time lower bound for satisfiability. Theor. Comput. Sci. 348(2-3): 311-320 (2005)
- [c14]Scott Diehl, Dieter van Melkebeek: Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. ICALP 2005: 982-993
- [i6]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)
- 2004
- [c13]Harry Buhrman, Troy Lee, Dieter van Melkebeek: Language Compression and Pseudorandom Generators. IEEE Conference on Computational Complexity 2004: 15-28
- [c12]
- [c11]Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek: Time-Space Tradeoff in Derandomizing Probabilistic Logspace. STACS 2004: 571-583
- [i5]Troy Lee, Dieter van Melkebeek, Harry Buhrman: Language Compression and Pseudorandom Generators. Electronic Colloquium on Computational Complexity (ECCC)(002) (2004)
- 2003
- [c10]Rahul Santhanam, Dieter van Melkebeek: Holographic Proofs and Derandomization. IEEE Conference on Computational Complexity 2003: 269-283
- 2002
- [j8]Thomas P. Hayes, Samuel Kutin, Dieter van Melkebeek: The Quantum Black-Box Complexity of Majority. Algorithmica 34(4): 480-501 (2002)
- [j7]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)
- [c9]Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. FOCS 2002: 669-678
- [i4]Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek: Power from Random Strings. Electronic Colloquium on Computational Complexity (ECCC)(028) (2002)
- 2001
- [j6]Dieter van Melkebeek: The Computational Complexity Column Time-Space Lower Bounds for Satisfiability. Bulletin of the EATCS 73: 57-77 (2001)
- [c8]Luis Antunes, Lance Fortnow, Dieter van Melkebeek: Computational Depth. IEEE Conference on Computational Complexity 2001: 266-273
- 2000
- [b1]Dieter van Melkebeek: Randomness and Completeness in Computational Complexity. Lecture Notes in Computer Science 1950, Springer 2000, ISBN 3-540-41492-4
- [j5]Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet: Separating Complexity Classes Using Autoreducibility. SIAM J. Comput. 29(5): 1497-1520 (2000)
- [j4]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)
- [j3]
- [c7]Lance Fortnow, Dieter van Melkebeek: Time-Space Tradeoffs for Nondeterministic Computation. IEEE Conference on Computational Complexity 2000: 2-13
- [c6]Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek: Optimal Proof Systems and Sparse Sets. STACS 2000: 407-418
- [i3]Lance Fortnow, Dieter van Melkebeek: Time-Space Tradeoffs for Nondeterministic Computation. Electronic Colloquium on Computational Complexity (ECCC) 7(28) (2000)
1990 – 1999
- 1999
- [j2]Harry Buhrman, Dieter van Melkebeek: Hard Sets Are Hard to Find. J. Comput. Syst. Sci. 59(2): 327-345 (1999)
- [c5]Adam Klivans, Dieter van Melkebeek: Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. STOC 1999: 659-667
- 1998
- [j1]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)
- [c4]Harry Buhrman, Dieter van Melkebeek: Hard Sets are Hard to Find. IEEE Conference on Computational Complexity 1998: 170-181
- [c3]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
- [i2]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)
- [i1]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)
- 1997
- [c2]Dieter van Melkebeek, Mitsunori Ogihara: Sparse Hard Sets for P. Advances in Algorithms, Languages, and Complexity 1997: 191-208
- 1996
- [c1]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
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-10-02 11:17 CEST by the dblp team