Former Research Area L: ‘Structural and algorithmic complexity’

The research of Research Area L is continued in Research Area KL as of 10/2012.

The interplay between mathematics and computation, and more specifically between optimisation and complexity, is central in our research area. Mathematical methods are employed to devise and analyse algorithms, and algorithmic ideas are applied in mathematical domains. On the one hand, we are designing efficient algorithms for various key problems, for example in combinatorial optimisation and number theory, some of which had been considered hitherto to be computationally intractable. On the other hand, recent years have witnessed dramatic progress in our understanding of the phenomena of efficient computation: new and deep techniques for establishing intrinsic intractability barriers, and new means for surmounting them. In most cases, some combinatorial structure needs to be explored to gain insight. Notions of efficient computation and complexity are also evolving into central paradigms in mathematics and its foundations. In a worldwide unique industrial cooperation, we are developing mathematical foundations and algorithms for designing next-generation computer chips, the most complex structures that mankind has ever developed.

To find out more, read a detailed description of the Research Area's achievements and goals.

Leaders of the Research Area