DIKU Bits: Solving Exponentially Hard Problems in Linear Time(?)

​Speaker

Jakob Nordström, associate professor in the Algorithms and Complexity section at DIKU.

Abstract

In an age when computers are everywhere – even in our pockets – complexity theory is the science of what such devices can achieve. A rich mathematical theory developed since the 1970s indicates that many important problems cannot be solved by efficient automated computation. But in parallel, applied research on these problems has led to methods that often works amazingly well in practice.

How is ths possible, and is there way to bridge the cap between the theory and practice of efficient computation?

Zooming in on Jakob Nordström

Which courses do you teach (BSc and MSc)?
I have just started, so we are still in the process of figuring this out. But I will teach “Discrete Mathematics and Formal Languages” this spring, and it is somewhat likely that sooner or later I will get involved in courses like “Logic in Computer Science” and/or “Computability and Complexity”.

Which technology/research/projects/startup are you excited to see the evolution of?
My own research, of course – otherwise I would not be doing what I am doing 😉 But artificial intelligence is a very exciting field, and I believe there are very interesting (and important) challenges remaining in getting computations to be verifiably correct, and in extracting explanations for how the results were reached.

What is your favorite sketch from the DIKUrevy?
This is one of the many exciting aspects of DIKU I look forward to learning more about in the future!