Dieter van Melkebeek

2008
49	EE	Jeff Kinne, Dieter van Melkebeek: Space Hierarchy Results for Randomized Models. STACS 2008: 433-444
48	EE	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	EE	Dieter van Melkebeek, Konstantin Pervyshev: A Generic Time Hierarchy with One Bit of Advice. Computational Complexity 16(2): 139-179 (2007)
46	EE	Dieter van Melkebeek: A Survey of Lower Bounds for Satisfiability and Related Problems. Electronic Colloquium on Computational Complexity (ECCC) 14(099): (2007)
45	EE	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	EE	Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek: 06111 Abstracts Collection -- Complexity of Boolean Functions. Complexity of Boolean Functions 2006
42	EE	Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, Rüdiger Reischuk: 06111 Executive Summary -- Complexity of Boolean Functions. Complexity of Boolean Functions 2006
41	EE	Dieter van Melkebeek, Konstantin Pervyshev: A Generic Time Hierarchy for Semantic Models With One Bit of Advice. Complexity of Boolean Functions 2006
40	EE	Scott Diehl, Dieter van Melkebeek: Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. Complexity of Boolean Functions 2006
39	EE	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	EE	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	EE	Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. SIAM J. Comput. 35(6): 1467-1493 (2006)
36	EE	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	EE	Luis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran: Computational depth: Concept and applications. Theor. Comput. Sci. 354(3): 391-404 (2006)
34	EE	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	EE	Scott Diehl, Dieter van Melkebeek: Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. ICALP 2005: 982-993
32	EE	Harry Buhrman, Troy Lee, Dieter van Melkebeek: Language compression and pseudorandom generators. Computational Complexity 14(3): 228-255 (2005)
31	EE	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	EE	Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas: Time-space lower bounds for satisfiability. J. ACM 52(6): 835-865 (2005)
29	EE	Dieter van Melkebeek, Rahul Santhanam: Holographic Proofs and Derandmization. SIAM J. Comput. 35(1): 59-90 (2005)
28	EE	Dieter van Melkebeek, Ran Raz: A time lower bound for satisfiability. Theor. Comput. Sci. 348(2-3): 311-320 (2005)
2004
27	EE	Dieter van Melkebeek, Ran Raz: A Time Lower Bound for Satisfiability. ICALP 2004: 971-982
26	EE	Harry Buhrman, Troy Lee, Dieter van Melkebeek: Language Compression and Pseudorandom Generators. IEEE Conference on Computational Complexity 2004: 15-28
25	EE	Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek: Time-Space Tradeoff in Derandomizing Probabilistic Logspace. STACS 2004: 571-583
24	EE	Troy Lee, Dieter van Melkebeek, Harry Buhrman: Language Compression and Pseudorandom Generators Electronic Colloquium on Computational Complexity (ECCC)(002): (2004)
2003
23	EE	Rahul Santhanam, Dieter van Melkebeek: Holographic Proofs and Derandomization. IEEE Conference on Computational Complexity 2003: 269-283
2002
22	EE	Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. FOCS 2002: 669-678
21	EE	Thomas P. Hayes, Samuel Kutin, Dieter van Melkebeek: The Quantum Black-Box Complexity of Majority. Algorithmica 34(4): 480-501 (2002)
20	EE	Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek: Power from Random Strings Electronic Colloquium on Computational Complexity (ECCC)(028): (2002)
19	EE	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	EE	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	EE	Lance Fortnow, Dieter van Melkebeek: Time-Space Tradeoffs for Nondeterministic Computation. IEEE Conference on Computational Complexity 2000: 2-13
14	EE	Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek: Optimal Proof Systems and Sparse Sets. STACS 2000: 407-418
13	EE	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	EE	Dieter van Melkebeek: The zero-one law holds for BPP. Theor. Comput. Sci. 244(1-2): 283-288 (2000)
1999
9	EE	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	EE	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	EE	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	EE	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	EE	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

1	Eric Allender	[20] [22] [37]
2	Luis Filipe Coelho Antunes (Luis Antunes)	[18] [35]
3	Harry Buhrman	[5] [6] [7] [8] [11] [12] [14] [20] [22] [24] [26] [32] [37]
4	Jin-yi Cai	[25] [34]
5	Venkatesan T. Chakaravarthy	[25] [34]
6	Scott Diehl	[33] [36] [40]
7	Stephen A. Fenner	[14]
8	Lance Fortnow	[12] [13] [14] [15] [18] [30] [35]
9	Thomas P. Hayes	[21]
10	Jeff Kinne	[45] [49]
11	Adam R. Klivans (Adam Klivans)	[4] [9] [19]
12	Michal Koucký	[20] [22] [37]
13	Matthias Krause	[42] [43] [44]
14	Samuel Kutin	[21]
15	Troy Lee	[24] [26] [32]
16	Richard J. Lipton	[30]
17	Mitsunori Ogihara (Mitsunori Ogiwara)	[2]
18	Konstantin Pervyshev	[31] [39] [41] [47]
19	Pavel Pudlák	[42] [43] [44]
20	Ran Raz	[27] [28]
21	Kenneth W. Regan	[5] [6] [11]
22	Rüdiger Reischuk	[42] [43] [44]
23	Detlef Ronneburger	[20] [22] [37]
24	Rahul Santhanam	[23] [29]
25	D. Sivakumar	[5] [6] [11]
26	Martin Strauss (Martin J. Strauss)	[5] [6] [11]
27	Leen Torenvliet	[12]
28	Anastasios Viglas	[30]
29	N. V. Vinodchandran (N. Variyam Vinodchandran)	[35]
30	Thomas Watson	[48]

Colors in the list of coauthors