Computer Sciences Dept.

Dieter van Melkebeek

Picture of Dieter van Melkebeek

Research Interests:

Theory of Computing, Computational Complexity.


Dieter van Melkebeek is a Professor of Computer Sciences. He completed his Ph.D. in 1999 at the University of Chicago, and was a postdoc at DIMACS and the Institute for Advanced Study (Princeton) before joining the faculty at the University of Wisconsin-Madison. He has held visiting appointments at CWI (Amsterdam), ENS (Paris), the Fields Institute (Toronto), Humboldt University (Berlin), MSRI (Berkeley), the Simons Institute (Berkeley), UPC (Barcelona), and the Weizmann Institute of Science (Rehovot).

Professor Van Melkebeek's research interests lie in computational complexity theory and the theory of computing. He has developed lower bounds for the resources needed to solve NP-complete problems, and studies the power of randomness in computation. He earned the 1999 ACM Doctoral Dissertation Award and an NSF CAREER award for his research.

Professor Van Melkebeek teaches algorithms and computational complexity theory at the undergraduate and graduate level. He also coaches the UW-Madison teams participating in the (ACM) International Collegiate Programming Contest, sending a team to the world finals every year since 2001.

Professor Van Melkebeek created the Computational Complexity Foundation, for which he received the ACM-SIGACT Distinguished Service Award. He chaired the program and steering committees of the Conference on Computational Complexity, and the ACM Doctoral Dissertation Award committee. He serves or has served on the editorials boards of the Leibniz International Proceedings in Informatics (LIPIcs), SIAM Journal on Computing, Computational Complexity, ACM Transactions on Computation Theory, and the Electronic Colloquium on Computational Complexity.

Computer Sciences | UW Home