Computational Challenges of Massive Data Sets and Randomness in Computation
J.UCS Special Issue on the First and Second Japanese-German Frontiers of Science Symposia

Jörg Rothe (Heinrich-Heine-Universität Düsseldorf, Germany)
rothe@cs.uni-duesseldorf.de

Hiroki Arimura (Hokkaido University, Japan)
arim@ist.hokudai.ac.jp

This special issue contains the contributions of some participants of the First and Second Japanese-German Frontiers of Science Symposia (JaGFoS). The First JaGFoS Symposium took place in Mainz, Germany, in January 2005, and its mathematics and computer science session was devoted to "Computational Challenges of Massive Data Sets." The Second JaGFoS Symposium took place in Shonan, Japan, in November 2005, and the topic of its mathematics and computer science session was "Randomness in Computation".

JaGFoS symposia are organized jointly by the Alexander von Humboldt Foundation and the Japan Society for the Promotion of Science (JSPS). The Humboldt Foundation has a wonderful tradition of organizing such bilateral meetings in which--during talks and discussions--the frontiers of science are explored by young leading scientists and researchers from only the two participating nations. For example, German-American Frontiers of Science Symposia (GAFoS), which are organized jointly by the Humboldt Foundation and the U.S. National Academy of Sciences, have been taking place for more than a decade now and have much helped to develop and strengthen the collaboration between researchers from the U.S.A. and Germany. 2005 was the year in which a similar series of frontiers of science symposia was launched in order to develop and strengthen the collaboration between Japanese and German researchers.

Frontiers of science symposia are not ordinary scientific conferences. They are very special both in their choice of topics and in the way these topics are presented. First, they are not restricted to some special scientific field, but rather they span a broad variety of sciences, simultaneously covering areas such as chemistry, physics, material sciences, mathematics and computer science, neurology, earth sciences, and social sciences. Each science has its own session, but all the participants take part in all the sessions.

So, for example, neurologists learn about the current research issues and trends in chemistry and computer science, and social scientists get to know up-to-date techniques and findings in astronomy and robotics. This means that, second, the talks in each session are not presented in a way that only the experts of the respective field can understand them; rather, they must be comprehensible to everybody in the audience, a truly challenging task for the speakers. Third, the invited speakers and participants present and discuss the most urgent and most interesting research issues, findings, accomplishments, and challenges of their fields. That is, each of the four talks in each session is devoted to some true "frontiers of science" theme. In addition to the talks, much weight is put on extensive and intense discussions, which are especially interesting due to the fact that researchers from quite different fields take part in them. Moreover, every participant has the opportunity to present his or her own research in a poster session.

In this J.UCS special issue, we have collected some survey and position papers related to the JaGFoS mathematics and computer science sessions. Not all the speakers from our sessions have contributed to this issue and not all the authors have been speakers at the JaGFoS symposia, though all authors were participants of at least one JaGFoS symposium. We are convinced that our selection of papers gives a very good impression of how the JaGFoS symposia are both broad in their interaction with other fields and deep in their attempt to explore the frontiers of research.

The first session, "Computational Challenges of Massive Data Sets", presents recent developments in machine learning (in particular, the Berlin Brain-Computer Interface, which is closely related to neurology), data mining methods, and sequential data assimilation with an application to numerical simulations of tsunamis. The second session, "Randomness in Computation", gives an introduction to cryptography and stresses the importance of randomness for capturing appropriate notions of security, introduces modern techniques of generating pseudorandom sequences, presents recent progress in quantum cryptography, shows that randomness is useful in membership tests for formal languages implicitly represented by boolean functions, surveys recent results on improving deterministic and randomized algorithms for computationally hard problems, and gives an overview of randomized complexity classes.

We acknowledge the support of the Humboldt Foundation and of JSPS, and we are particularly grateful to Dr. Katja Hartmann and Ms. Anke Teubner from the Humboldt Foundation and to Ms. Kumiko Tansho from JSPS. We also thank Ms. Dana Kaiser for her great editorial help in preparing this special issue.