Foundations of Exact Algorithms

Vision and Research Strategy

In their early stages, computing devices were painstakingly slow, huge, and expensive. This, however, has changed and is still changing at an exponential rate – we can see the results of Moore's law everywhere: Computing devices are ubiquitous, and they are solving tasks more complex than ever before. The research group Foundations of Exact Algorithms in the cluster of excellence at Saarland University focuses on the theoretical aspects of computer science, and in particular those aspects that have become relevant due to the progression of Moore's law.

Exact Algorithms is an area whose goal is to pin down the exact complexity of fundamental NP-complete problems such as the satisfiability problem and hard graph problems. In the past, these problems got dismissed as too hard for computers to solve completely, which lead researchers to evade their inherent complexity in one of three ways:

  1. Researchers settled for approximate solutions, in cases where such approximation is feasible,
  2. Researchers solved the problem only in special cases, where the problem is feasible, and
  3. Researchers settled for heuristics, that is, algorithms that work well in practice but that do not have provable running time or correctness guarantees.

In recent years, a fourth method for dealing with NP-complete problems was made possible by Moore's law, at least when the instances are not too large: Computers can now solve NP-complete problems fully, head-on, without any loss in quality – naturally, this is only believed to be possible with an exponentional asymptotic running time. Our group wishes to understand the precise rate at which the running time of such algorithms must grow.

 

Composition of the Group

This group was founded at the Cluster of Excellence in September 2014.

PhD students: Cornelius Brand (since June 2016) and Marc Roth (since August 2016).

Postdocs: Navid Talebanfard (since July 2016)

If you would like to join the group as a PhD student or as a postdoc, please contact the group leader.

Collaborators

Dr. Holger Dell

Dr. Holger Dell

Holger Dell is the head of the Independent Research Group Foundations of Exact Algorithms.

Fon: +49 681 302 4447

Publications