 | 2009 |
|---|
| 52 |       | Jeff Kinne,
Dieter van Melkebeek,
Ronen Shaltiel:
Pseudorandom Generators and Typically-Correct Derandomization.
APPROX-RANDOM 2009: 574-587 |
| 51 | | Scott Diehl,
Dieter van Melkebeek,
Ryan Williams:
An Improved Time-Space Lower Bound for Tautologies.
COCOON 2009: 429-438 |
| 50 | | 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) |
| 2008 |
|---|
| 49 | | Jeff Kinne,
Dieter van Melkebeek:
Space Hierarchy Results for Randomized Models.
STACS 2008: 433-444 |
| 48 | | 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 |
|---|
| 47 | | Dieter van Melkebeek,
Konstantin Pervyshev:
A Generic Time Hierarchy with One Bit of Advice.
Computational Complexity 16(2): 139-179 (2007) |
| 46 | | Dieter van Melkebeek:
A Survey of Lower Bounds for Satisfiability and Related Problems.
Electronic Colloquium on Computational Complexity (ECCC) 14(099): (2007) |
| 45 | | Jeff Kinne,
Dieter van Melkebeek:
Space Hierarchy Results for Randomized and Other Semantic Models.
Electronic Colloquium on Computational Complexity (ECCC) 14(134): (2007) |
| 2006 |
|---|
| 44 |  | Matthias Krause,
Pavel Pudlák,
Rüdiger Reischuk,
Dieter van Melkebeek:
Complexity of Boolean Functions, 12.03. - 17.03.2006
Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2006 |
| 43 | | Matthias Krause,
Pavel Pudlák,
Rüdiger Reischuk,
Dieter van Melkebeek:
06111 Abstracts Collection -- Complexity of Boolean Functions.
Complexity of Boolean Functions 2006 |
| 42 | | Matthias Krause,
Dieter van Melkebeek,
Pavel Pudlák,
Rüdiger Reischuk:
06111 Executive Summary -- Complexity of Boolean Functions.
Complexity of Boolean Functions 2006 |
| 41 | | Dieter van Melkebeek,
Konstantin Pervyshev:
A Generic Time Hierarchy for Semantic Models With One Bit of Advice.
Complexity of Boolean Functions 2006 |
| 40 | | Scott Diehl,
Dieter van Melkebeek:
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines.
Complexity of Boolean Functions 2006 |
| 39 | | 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 |
| 38 | | 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) |
| 37 | | Eric Allender,
Harry Buhrman,
Michal Koucký,
Dieter van Melkebeek,
Detlef Ronneburger:
Power from Random Strings.
SIAM J. Comput. 35(6): 1467-1493 (2006) |
| 36 | | 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) |
| 35 | | Luis Antunes,
Lance Fortnow,
Dieter van Melkebeek,
N. V. Vinodchandran:
Computational depth: Concept and applications.
Theor. Comput. Sci. 354(3): 391-404 (2006) |
| 34 | | Jin-yi Cai,
Venkatesan T. Chakaravarthy,
Dieter van Melkebeek:
Time-Space Tradeoff in Derandomizing Probabilistic Logspace.
Theory Comput. Syst. 39(1): 189-208 (2006) |
| 2005 |
|---|
| 33 | | Scott Diehl,
Dieter van Melkebeek:
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines.
ICALP 2005: 982-993 |
| 32 | | Harry Buhrman,
Troy Lee,
Dieter van Melkebeek:
Language compression and pseudorandom generators.
Computational Complexity 14(3): 228-255 (2005) |
| 31 | | 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) |
| 30 | | Lance Fortnow,
Richard J. Lipton,
Dieter van Melkebeek,
Anastasios Viglas:
Time-space lower bounds for satisfiability.
J. ACM 52(6): 835-865 (2005) |
| 29 | | Dieter van Melkebeek,
Rahul Santhanam:
Holographic Proofs and Derandmization.
SIAM J. Comput. 35(1): 59-90 (2005) |
| 28 | | Dieter van Melkebeek,
Ran Raz:
A time lower bound for satisfiability.
Theor. Comput. Sci. 348(2-3): 311-320 (2005) |
| 2004 |
|---|
| 27 | | Dieter van Melkebeek,
Ran Raz:
A Time Lower Bound for Satisfiability.
ICALP 2004: 971-982 |
| 26 | | Harry Buhrman,
Troy Lee,
Dieter van Melkebeek:
Language Compression and Pseudorandom Generators.
IEEE Conference on Computational Complexity 2004: 15-28 |
| 25 | | Jin-yi Cai,
Venkatesan T. Chakaravarthy,
Dieter van Melkebeek:
Time-Space Tradeoff in Derandomizing Probabilistic Logspace.
STACS 2004: 571-583 |
| 24 | | Troy Lee,
Dieter van Melkebeek,
Harry Buhrman:
Language Compression and Pseudorandom Generators
Electronic Colloquium on Computational Complexity (ECCC)(002): (2004) |
| 2003 |
|---|
| 23 | | Rahul Santhanam,
Dieter van Melkebeek:
Holographic Proofs and Derandomization.
IEEE Conference on Computational Complexity 2003: 269-283 |
| 2002 |
|---|
| 22 | | Eric Allender,
Harry Buhrman,
Michal Koucký,
Dieter van Melkebeek,
Detlef Ronneburger:
Power from Random Strings.
FOCS 2002: 669-678 |
| 21 | | Thomas P. Hayes,
Samuel Kutin,
Dieter van Melkebeek:
The Quantum Black-Box Complexity of Majority.
Algorithmica 34(4): 480-501 (2002) |
| 20 | | Eric Allender,
Harry Buhrman,
Michal Koucký,
Detlef Ronneburger,
Dieter van Melkebeek:
Power from Random Strings
Electronic Colloquium on Computational Complexity (ECCC)(028): (2002) |
| 19 | | 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) |
| 2001 |
|---|
| 18 | | Luis Antunes,
Lance Fortnow,
Dieter van Melkebeek:
Computational Depth.
IEEE Conference on Computational Complexity 2001: 266-273 |
| 17 | | Dieter van Melkebeek:
The Computational Complexity Column Time-Space Lower Bounds for Satisfiability.
Bulletin of the EATCS 73: 57-77 (2001) |
| 2000 |
|---|
| 16 | | Dieter van Melkebeek:
Randomness and Completeness in Computational Complexity
Springer 2000 |
| 15 | | Lance Fortnow,
Dieter van Melkebeek:
Time-Space Tradeoffs for Nondeterministic Computation.
IEEE Conference on Computational Complexity 2000: 2-13 |
| 14 | | Harry Buhrman,
Stephen A. Fenner,
Lance Fortnow,
Dieter van Melkebeek:
Optimal Proof Systems and Sparse Sets.
STACS 2000: 407-418 |
| 13 | | Lance Fortnow,
Dieter van Melkebeek:
Time-Space Tradeoffs for Nondeterministic Computation
Electronic Colloquium on Computational Complexity (ECCC) 7(28): (2000) |
| 12 | | Harry Buhrman,
Lance Fortnow,
Dieter van Melkebeek,
Leen Torenvliet:
Separating Complexity Classes Using Autoreducibility.
SIAM J. Comput. 29(5): 1497-1520 (2000) |
| 11 | | 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) |
| 10 | | Dieter van Melkebeek:
The zero-one law holds for BPP.
Theor. Comput. Sci. 244(1-2): 283-288 (2000) |
| 1999 |
|---|
| 9 | | Adam Klivans,
Dieter van Melkebeek:
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.
STOC 1999: 659-667 |
| 8 | | Harry Buhrman,
Dieter van Melkebeek:
Hard Sets Are Hard to Find.
J. Comput. Syst. Sci. 59(2): 327-345 (1999) |
| 1998 |
|---|
| 7 | | Harry Buhrman,
Dieter van Melkebeek:
Hard Sets are Hard to Find.
IEEE Conference on Computational Complexity 1998: 170-181 |
| 6 | | 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 |
| 5 | | 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) |
| 4 | | 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) |
| 3 | | 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) |
| 1997 |
|---|
| 2 | | Dieter van Melkebeek,
Mitsunori Ogihara:
Sparse Hard Sets for P.
Advances in Algorithms, Languages, and Complexity 1997: 191-208 |
| 1996 |
|---|
| 1 | | 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 |
