This award supports a group of three U.S. computer scientists coordinated by Professor Steven Homer of Boston University to collaborate with Professor Peter van Emde Boas and others of the Department of Mathematics and Computer Science of the University of Amsterdam, the Netherlands. Their research will focus on several current topics in the theory of computation, including structural complexity theory and Kolmogorov complexity theory. The planned collaboration will be expedited by several reciprocal working meetings among the participants that will give opportunities to local young researchers and particularly graduate students to benefit from participation in the discussions. This research lies on the boundary between mathematics and computer science. The various research partnerships among the seven participants should yield significant results in several central areas of complexity theory. The complementary expertise contributed by the U.S. and Dutch participants has the potential to contribute insights and connections which would not emerge without the cooperative interactions.
