Dieter van Melkebeek Home Page Coauthor index DBLP Vis pubzone.org

List of publications from the DBLP Bibliography Server - FAQ
Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

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

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

Colors in the list of coauthors

Copyright © Sun Mar 14 22:39:24 2010 by Michael Ley (ley@uni-trier.de)