Algorithm Theory studies the power and limits of algorithms from a mathematical point of view.
On one hand, the goal of Algorithm Design is to develop algorithms that are provably "efficient", i.e. that use a limited amount of the available resources (time, memory, bandwidth, etc.). On the other hand, the aim of Complexity Theory is to provide lower bounds on the amount of the mentioned resources that every algorithm needs to use.
The Algorithm and Complexity group at IDSIA is doing research in several areas of Theoretical Computer Science. One of the main areas of expertise is Approximation Algorithms. Here the goal is to design a fast algorithm that solves a (typically "hard") optimization problem "approximately", i.e. that provides a solution of cost (provably) close to the optimal one. In particular, the group is active in the area of Network Design and Scheduling.
- Network Design