Algorithms and Complexity

Our researchers study the inherent difficulty of computational problems on a foundational level. This entails finding links between the classification and counting of basic mathematical structures, the size of descriptions of objects and of mathematical proofs, and descriptions of algorithms and bounds for their complexity. It can involve the development of new algorithms, or rigorous mathematical proofs that certain problems cannot be solved efficiently under standard assumptions from complexity theory, such as P ≠ NP. Our researchers also specialise in modern algorithmic paradigms such as parameterised algorithms and fine-grained complexity theory.

We work closely with mathematicians in combinatorics and information theory to find and count new and complex structures and to relate them to hard instances of computational problems.

Using-adversarial-nets-random.png Pasquale Malacaria, with permission