Dieter van Melkebeek Associate Professor

List of Publications

• H. Dell and D. van Melkebeek. Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. In preparation.
• S. Aaronson and D. van Melkebeek. A note on circuit lower bounds from derandomization. In preparation.
• J. Kinne, D. van Melkebeek, and R. Shaltiel. Pseudorandom Generators and Typically-Correct Derandomization. In Proceedings of the 13th International Workshop on Randomization and Computation, pages 574-587, 2009. Invited to the special journal issue for selected papers from the conference.
• S. Diehl, D. van Melkebeek, and R. Williams. An Improved Time-Space Lower Bound for Tautologies. In Proceedings of the 15th International Computing and Combinatorics Conference, pages 429-438, 2009. Invited to the special journal issue for selected papers from the conference.
• D. van Melkebeek and T. Watson. A Quantum Time-Space Lower Bound for the Counting Hierarchy. Manuscript, 2008.
• J. Kinne and D. van Melkebeek. Space Hierarchy Results for Randomized Models. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, pages 433-444, 2008.
• D. van Melkebeek. A Survey of Lower Bounds for Satisfiability and Related Problems. Foundations and Trends in Theoretical Computer Science, 2: 197-303, 2007.
• D. van Melkebeek and K. Pervyshev. A Generic Time Hierarchy for Semantic Models With One Bit of Advice. Computational Complexity, 16: 139-179, 2007. Special issue for selected papers from the 21st Conference on Computational Complexity.
• S. Diehl and D. van Melkebeek. Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. SIAM Journal on Computing, 36: 563-594, 2006.
• D. van Melkebeek and K. Pervyshev. A Generic Time Hierarchy for Semantic Models With One Bit of Advice. In Proceedings of the 21st IEEE Conference on Computational Complexity, pages 129-142, 2006.
• E. Allender, H. Buhrman, M. Koucky, D. van Melkebeek, and D. Ronneburger. Power from Random Strings. SIAM Journal on Computing, 35: 1467-1493, 2006.
• L. Antunes, L. Fortnow, D. van Melkebeek, and N. Vinodchandran. Computational Depth: Concept and Applications. Theoretical Computer Science, 354: 391-404, 2006. Special issue for selected papers from the 14th International Symposium on Fundamentals of Computation Theory.
• J.-Y. Cai, V. Chakaravarthy, and D. van Melkebeek. Time-Space Tradeoff In Derandomizing Probabilistic Logspace. Theory of Computing Systems, 39: 189-208, 2006. Special issue for selected papers from the 21st International Symposium on Theoretical Aspects of Computer Science.
• L. Fortnow, R. Lipton, D. van Melkebeek, and A. Viglas. Time-Space Lower Bounds for Satisfiability. Journal of the ACM, 52: 835-865, 2005.
• S. Diehl and D. van Melkebeek. Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, pages 982-993, 2005.
• D. van Melkebeek and R. Santhanam. Holographic Proofs and Derandomization. SIAM Journal on Computing, 35: 59-90, 2005.
• D. van Melkebeek and R. Raz. A Time Lower Bound for Satisfiability. Theoretical Computer Science, 348: 311-320, 2005. Special issue for selected papers from the 31st International Colloquium on Automata, Languages and Programming.
• H. Buhrman, T. Lee, and D. van Melkebeek. Language Compression and Pseudorandom Generators. Computational Complexity, 14: 228-255, 2005. Special issue for selected papers from the 19th Annual Conference on Computational Complexity.
• A. Lal and D. van Melkebeek. Graph Isomorphism for Colored Graphs with Color Multiplicity Bounded by 3. University of Wisconsin-Madison, Department of Computer Sciences, Technical Report 1523, 2005.
• D. van Melkebeek and R. Raz. A Time Lower Bound for Satisfiability. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming, pages 971-982, 2004.
• H. Buhrman, T. Lee, and D. van Melkebeek. Language Compression and Pseudorandom Generators. In Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pages 15-28, 2004.
• D. van Melkebeek. Time-Space Lower Bounds for NP-Complete Problems. In G. Paun, G. Rozenberg, and A. Salomaa (eds.), Current Trends in Theoretical Computer Science, pages 265-291, World Scientific, 2004.
• J.-Y. Cai, V. Chakaravarthy, and D. van Melkebeek. Time-Space Tradeoff In Derandomizing Probabilistic Logspace. In Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science, pages 571-583, 2004.
• D. van Melkebeek and R. Santhanam. Holographic Proofs and Derandomization. In Proceedings of the 18th IEEE Conference on Computational Complexity, pages 269-283, 2003.
• E. Allender, H. Buhrman, M. Koucky, D. van Melkebeek, and D. Ronneburger. Power from Random Strings. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, pages 669-678, 2002.
• A. Klivans and D. van Melkebeek. Graph Nonisomorphism Has Subexponential Size Proofs Unless The Polynomial-Time Hierarchy Collapses. SIAM Journal on Computing, 31: 1501-1526, 2002.
• T. Hayes, S. Kutin, and D. van Melkebeek. On the Quantum Black-Box Complexity of Majority. Algorithmica, 34: 480-501, 2002. Special issue for selected papers on quantum information processing.
• L. Antunes, L. Fortnow, and D. van Melkebeek. Computational Depth. In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 266-273, 2001.
• D. van Melkebeek. Time-Space Lower Bounds for Satisfiability. Bulletin of the European Association for Theoretical Computer Science, 73: 57-77, 2001.
• D. van Melkebeek. Randomness and Completeness in Computational Complexity. ACM Doctoral Dissertation Award Series, LNCS 1950. Springer-Verlag, 2000.
• L. Fortnow and D. van Melkebeek. Time-Space Tradeoffs for Nondeterministic Computation. In Proceedings of the 15th IEEE Conference on Computational Complexity, pages 2-13, 2000.
• D. van Melkebeek. The Zero-One Law Holds for BPP. Theoretical Computer Science, 244(1-2): 283-288, 2000.
• H. Buhrman, D. van Melkebeek, K. Regan, D. Sivakumar, and M. Strauss. A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem. SIAM Journal on Computing, 30(2): 576-601, 2000.
• H. Buhrman, L. Fortnow, D. van Melkebeek, and L. Torenvliet. Separating Complexity Classes using Autoreducibility. SIAM Journal on Computing, 29(5): 1497-1520, 2000.
• H. Buhrman, L. Fortnow, S. Fenner, and D. van Melkebeek. Optimal Proof Systems and Sparse Sets. In Proceedings of the 17th International Symposium on Theoretical Aspects of Computer Science, pages 407-418, 2000.
• H. Buhrman and D. van Melkebeek. Hard Sets Are Hard to Find. Journal of Computer and System Sciences, 59(2): 327-345, 1999. Special issue for selected papers from the 13th Conference on Computational Complexity.
• A. Klivans and D. van Melkebeek. Graph Nonisomorphism Has Subexponential Size Proofs Unless The Polynomial-Time Hierarchy Collapses. In Proceedings of 31st ACM Symposium on Theory of Computing, pages 659-667, 1999.
• D. van Melkebeek. Deterministic and Randomized Bounded Truth-table Reductions of P, NL, and L to Sparse Sets. Journal of Computer and System Sciences, 57(2): 213-232, 1998. Special issue for selected papers from the 11th Conference on Computational Complexity.
• D. van Melkebeek. Derandomizing Arthur-Merlin Games. The University of Chicago, Department of Computer Science, Technical Report TR-98-08, July 1998.
• H. Buhrman and D. van Melkebeek. Hard Sets Are Hard to Find. In Proceedings of the 13th IEEE Conference on Computational Complexity , pages 170-181, 1998.
• H. Buhrman, D. van Melkebeek, K. Regan, D. Sivakumar, and M. Strauss. A Generalization of Resource-Bounded Measure, With an Application. In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science , pages 161-171, 1998.
• D. van Melkebeek and M. Ogihara. Sparse Hard Sets for P. In: Du, D.-Z. and K.-I Ko (eds.), Advances in Languages, Algorithms, and Complexity, ISBN 0-7923-4396-4, p. 191-208. Kluwer Academic Publishers, 1997.
• D. van Melkebeek. Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L. In Proceedings of the 11th IEEE Conference on Computational Complexity , pages 88-96, 1996.
• D. van Melkebeek and A. Bultheel. On the Relation between Iterated Function Systems and Partitioned Iterated Function Systems. Katholieke Universiteit Leuven, Departement Computerwetenschappen, Technical Report TW 240, 1996.
• D. van Melkebeek and M. Van Barel. Julia Sets and the Mandelbrot Set. In: Warrinier, A. (ed.), Why Is the Blue Sky Blue? On Order, Chaos and Fractals, ISBN 90-6186-597-2, p. 67-87. Universitaire Pers Leuven, 1994. Reference translated from Dutch.
• D. van Melkebeek and A. Bultheel. Invariant Finite Borel Measures for Rational Functions on the Riemann Sphere. Journal de Mathématiques Pures et Appliquées , 73(2): 191-221, 1994.
• D. van Melkebeek and A. Bultheel. Block Orthogonal Systems for Symmetric P-forms. Journal of Computational and Applied Mathematics, 49(1-3): 305-316, 1993.