The research team working on this project consists of Lic.Sc. (Tech.) Satu Elisa Schaeffer and Professor Pekka Orponen. The work will be carried out at the Laboratory for Theoretical Computer Science of the Helsinki University of Technology.

Satu Elisa Schaeffer has been pursuing her doctoral studies on the topic of nonuniform random graphs under the supervision of Pekka Orponen since Spring 2002. Her Licentiate thesis Properties of Nonuniform Random Graph Models was accepted with distinction (5/5) by the council of the Department of Computer Science and Engineering in April 2003. Presently she is continuing with original research in the field, especially in clustering and sampling algorithms for the Web graph, with the eventual goal of completing her doctoral dissertation in Spring 2006. Since August 2002, Schaeffer has been working as a researcher in the research consortium Stochastic Adaptive Dynamics of Complex Systems (STADYCS), funded by the Academy of Finland as part of its Mathematical Methods and Modelling in the Sciences (MaDaMe) programme. This programme terminated in December 2003. The publications of Schaeffer (maiden name Virtanen) pertinent to the STADYCS project include her Lic.Sc. thesis [Virt03a], and her talk on novel online graph clustering methods at Second Workshop on Algorithms and Models for the Web-Graph (WAW 2003) [Virt03b] as well as a poster at a NIPS workshop on Robust Communication Dynamics in Complex Networks [Virt03c].

Pekka Orponen has been a Professor of Theoretical Computer Science at the Helsinki University of Technology since September 2001. (His former employment was at the Department of Mathematics of the University of Jyväskylä.) He was the coordinator of the MaDaMe STADYCS consortium, and also a partner in the consortium Networks and Architectures for Proactive Systems (NAPS), funded by the Academy of Finland as part of its research programme on Proactive Computing (PROACT, 2003-2005). His research interests are in the areas of computational and structural complexity, and their application to the design of efficient algorithms. His recent publications most relevant to the present project include two applications of stochastic approximation methods to a difficult problem in computational statistics [RoOO03], and to the solution of very large instances of the satisfiability problem [SeOr03]. Possibly worth mentioning are also the typeset lecture notes from an advanced course on stochastic algorithms taught at HUT in the Spring term of 2003 [Orpo03]. (Orponen's former work on the computational theory of neural network models is summarised in the forthcoming major survey article [SiOr03].) In the academic year 2003-2004, Orponen is on sabbatical supported by a senior scientist appropriation from the Academy of Finland, and will thus be able to concentrate full time on research work in the projects mentioned.

The Laboratory for Theoretical Computer Science is one of the six laboratories constituting the Department of Computer Science and Engineering at the Helsinki University of Technology. The work at the laboratory is highly research intensive. The present staff consists of five professors, three senior lecturers, and 29 researchers supported on external, competitive funding (mainly research projects from the Academy of Finland and the Finnish National Technology Agency TEKES, and graduate student positions funded by the Finnish Ministry of Education.) The annual budget of the laboratory is approximately 1.6 million euros, out of which less than 40 percent comes from HUT. Work at the laboratory is structured to cover five main areas of theoretical computer science and its applications: computational complexity and combinatorics, computational logic, verification, mobility management and cryptology. The computational complexity and combinatorics group, directed by Pekka Orponen, consists at the moment of seven people, but the boundaries between the groups at the laboratory are not strict, and there are several naturally overlapping interest areas.

Collaboration

Within the TCS laboratory, the project has natural collaboration with the group on mobility management (Prof. Hannu Kari) on the topics of routing and node clustering for mobile ad hoc networks, and also with the computational logic group (Prof. Ilkka Niemelä) on the general topic of stochastic algorithms for nonuniform structures (which can equally well be graphs or formulas). In the area of telecommunication network applications, especially ad hoc networks, further opportunities are provided by the NAPS consortium in the direction of the Department of Computer Science at the University of Helsinki and the Helsinki Institute for Information Technology HIIT (Doc. Patrik Floréen), and in the direction of the HUT Networking laboratory (Prof. Jorma Virtamo). Also within the HUT DCSE, Satu Elisa Schaeffer has already initiated discussions in the area of clustering methods with researchers at the Laboratory of Computer and Information Science.

More broadly within Finland, the project belongs to the research network on complex systems spanned by the STADYCS consortium. Partners in this consortium with an expressed interest in nonuniform networks include the Ecology (Academy Prof. Ilkka Hanski), Economics (Academy Prof. Seppo Honkapohja), Mathematics (Doc. Kari Eloranta) and Computational Engineering (Academy Prof. Kimmo Kaski) groups. There are also obvious theoretical and applied questions of interest to the other groups (Biomathematics/Dr. Éva Kísdi, Physics/Prof. Tapio Ala-Nissilä), but with these the matter has not yet been explicitly discussed.

Internationally, Pekka Orponen has good contacts to Prof. Cris Moore at the Santa Fe Institute for Complex System Studies, and will probably be spending some months in the Spring of 2004 visiting him in New Mexico. At the European level, a network of relevant contacts exists within the algorithms and complexity research community (e.g. Prof. Mark Jerrum/Edinburgh, Prof. Josep Díaz/Barcelona), but at this level there are at the moment no concrete collaborative initiatives. This situation is likely to change as the project progresses.

Moreover, Satu Elisa Schaeffer will spend one third of the project term, namely the academic year 2005, in Santiago, Chile, as an exchange student sponsored by the Rotary Foundation's Ambassadorial Scholarship, studying in the University of Chile.