(aside image)

Combinatorial Algorithms and Computation (CAC)

This page is no longer updated. Please refer to the new pages of the Combinatorial Algorithms group and the Natural Computation group.

Work in the area of combinatorial algorithms and computation theory at the department is structured along three research themes: Modern Algorithmics, Computational Models and Mechanics, and Algorithmics for Data Security.

Modern Algorithmics

The members of the Modern Algorithmics team are: Alumni of the team include:

The team applies combinatorial and complexity-theoretic methods to the solution of algorithmic problems in challenging operating environments, often characterised by incomplete information about the global system state.

Recent areas of research have been online algorithms for production planning applications, and energy-awareness issues in ad hoc and sensor networks, such as the design and analysis of energy-efficient routing methods, and lifetime-maximising network topology control.

In 2003-2005, the team was a member of the consortium Networking and Architecture for Proactive Systems (NAPS), funded by the Academy of Finland as part of its Proactive Computing (PROACT) research programme. The other partners in this consortium were the Networking Laboratory at TKK and the Department of Computer Science of the University of Helsinki. In 2004-2006, a connected project on Algorithms and Combinatorics for Sensor Networks (ACSENT) was funded by the Academy of Finland. In 2009, research collaboration on online optimisation methods was initiated with the Department of Engineering Design and Production of TKK (now part of Aalto University). In 2009-2011 two coordinated projects in this area were executed, one on fundamental methodology supported by the Academy of Finland, and another on industrial applications supported by Tekes, the Finnish Funding Agency for Technology and Innovation.

In summer 2012, a pilot project was pursued on using techniques from distributed algorithmics to coordinate the actions of a small ensemble of low-cost swarm robots. For more details and a video clip, see the kilobots page by the group's summer intern Antti Halme.

Teaching

Computational Models and Mechanics

The members of the Computational Models and Mechanics team are: Alumni of the team include:

The team studies methods for the solution of computational problems in structurally complex state spaces. The main focus is on techniques that are algorithmically relatively simple, but which adapt effectively to the characteristics of the problem instance at hand. The specific topics considered include e.g. the behaviour of graph algorithms on small-world networks and the design and analysis of stochastic search methods for complex optimisation landscapes. A recent area of interest have been algorithmic issues related to the design of self-assembling nanoscale structures.

The team was the coordinating partner in the multidisciplinary 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) research programme. The other partners in this consortium were the Laboratories of Physics, Mathematics, and Computational Engineering at TKK, the Departments of Mathematics, Economics, and Ecology and Systematics at the University of Helsinki, and the Department of Mathematics at the University of Turku. In 2004-2006, the team had another project funded by the Academy of Finland, Algorithms for Nonuniform Networks (ANNE). Presently, the team works in close collaboration with the groups of Prof. Erik Aurell (Aalto/ICS and KTH) and Prof. Mikko Alava (Aalto/Engineering Physics), as partners in Erik Aurell's FiDiPro consortium, supported by the Academy of Finland and Aalto University.

Teaching

Algorithmics for Data Security

The members of the Algorithmics for Data Security team are: Alumni of the team include: The team works on advanced static and dynamic malware-detection methods on host-based systems. This includes analysis of e.g. call graphs of malware executables and dynamic sandbox execution data, provided by the team's industrial partners. The research is part of the ICT SHOK Future Internet Programme, WP6 Data Security.