Research Area KL: ‘Algorithms, combinatorics, and complexity’
The Research Area KL started in 11/2012.
Algorithms and complexity are intimately connected subjects. The combination of the two previously separate research areas K and L led to refocusing on central themes in the interplay between algorithms, combinatorics, and complexity.
The interaction between mathematics and computation, and more specifically between optimization and complexity, is central in our research area. Mathematical methods are employed to devise and analyze algorithms, and algorithmic ideas are applied in mathematical domains. On the one hand, efficient algorithms for various key problems are designed in this Research Area; 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, this Research Area develops mathematical foundations and algorithms for designing next-generation computer chips, the most complex structures that mankind has ever developed.