Dieter van Melkebeek Professor

List of Publications

• I. Hu, D. van Melkebeek, and A. Morgan. Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees. Theory of Computing, 53 pages, to appear.
• I. Hu, D. van Melkebeek, and A. Morgan. Polynomial Identity Testing via Evaluation of Rational Functions. Theory of Computing, 20: 1-70, 2024.
• D. van Melkebeek and N. Mocelin Sdroievski. Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols. In Proceedings of the 43rd Conference on Foundations of Software Technology and Theoretical Computer Science, pages 29:1-29:22, 2023.
• D. van Melkebeek and N. Mocelin Sdroievski. Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols . In Proceedings of the 38th Computational Complexity Conference, pages 17:1-17:36, 2023.
• I. Hu, D. van Melkebeek, and A. Morgan. Query Complexity of Inversion Minimization on Trees. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 2836-2866, 2023.
• D. van Melkebeek and A. Morgan. Polynomial Identity Testing via Evaluation of Rational Functions. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference, pages 119:1-24, 2022.
• D. van Melkebeek and G. Prakriya. Derandomizing Isolation in Space-Bounded Settings. SIAM Journal on Computing, 48: 979-1021, 2019.
• E. Allender, J. Grochow, D. van Melkebeek, C. Moore, and A. Morgan. Minimum Circuit Size, Graph Isomorphism, and Related Problems. SIAM Journal on Computing, 47: 1339-1372, 2018.
• E. Allender, J. Grochow, D. van Melkebeek, C. Moore, and A. Morgan. Minimum Circuit Size, Graph Isomorphism, and Related Problems. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference, pages 20: 1-20, 2018.
• D. van Melkebeek and G. Prakriya. Derandomizing Isolation in Space-Bounded Settings. In Proceedings of the 32nd Computational Complexity Conference, pages 17: 1-33, 2017.
• B. Aydinlioglu and D. van Melkebeek. Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. Computational Complexity, 26: 79-118, 2017.
• M. Anderson, D. van Melkebeek, and I. Volkovich. Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. Computational Complexity, 24: 695-776, 2015.
• H. Dell and D. van Melkebeek. Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. Journal of the ACM, 61(4), 27 pages, 2014.
• H. Dell, V. Kabanets, D. van Melkebeek, and O. Watanabe. Is Valiant-Vazirani's Isolation Probability Improvable? Computational Complexity, 22: 345-383, 2013. Special issue for selected papers from the 27th IEEE Conference on Computational Complexity.
• M. Anderson, D. van Melkebeek, N. Schweikardt, and L. Segoufin. Locality from Circuit Lower Bounds. SIAM Journal on Computing, 41: 1481-1523, 2012.
• B. Aydinlioglu and D. van Melkebeek. Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. In Proceedings of the 27th IEEE Conference on Computational Complexity, pages 269-279, 2012.
• H. Dell, V. Kabanets, D. van Melkebeek, and O. Watanabe. Is Valiant-Vazirani's Isolation Probability Improvable? In Proceedings of the 27th IEEE Conference on Computational Complexity, pages 10-20, 2012.
• G. Karakostas, J. Kinne, and D. van Melkebeek. On Derandomization and Average-Case Complexity of Monotone Functions. Theoretical Computer Science, 434: 35-44, 2012.
• J. Kinne, D. van Melkebeek, and R. Shaltiel. Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. Computational Complexity, 21: 3-61, 2012. Special journal issue for selected papers from the 13th International Workshop on Randomization and Computation.
• D. van Melkebeek and T. Watson. Time-Space Efficient Simulations of Quantum Computations. Theory of Computing, 8: 1-51, 2012.
• M. Anderson, D. van Melkebeek, N. Schweikardt, and L. Segoufin. Locality of queries definable in invariant first-order logic with arbitrary built-in predicates. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming, Part II, pages 368-379, 2011.
• M. Anderson, D. van Melkebeek, and I. Volkovich. Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. In Proceedings of the 26th IEEE Conference on Computational Complexity, pages 273-282, 2011.
• S. Aaronson and D. van Melkebeek. On Circuit Lower Bounds from Derandomization. Theory of Computing, 7: 177-184, 2011.
• S. Diehl, D. van Melkebeek, and R. Williams. An Improved Time-Space Lower Bound for Tautologies. Journal of Combinatorial Optimization, 22(3): 325-338, 2011. Special issue for selected papers from the 15th International Computing and Combinatorics Conference.
• S. Aaronson, B. Aydinlioglu, H. Buhrman, J. Hitchcock, and D. van Melkebeek. A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games, Electronic Colloquium on Computational Complexity, Technical Report ECCC-TR 10-174, 2010.
• H. Dell and D. van Melkebeek. Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 251-260, 2010.
• J. Kinne and D. van Melkebeek. Space Hierarchy Results for Randomized and Other Semantic Models. Computational Complexity, 19: 423-475, 2010.
• 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.
• 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.
• 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 the 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.