Jakob Nordström

Computers are everywhere today—at work, in our cars, in our living rooms, and in our pockets—and have changed the world beyond our wildest imagination. Yet these marvelous devices are, at the core, amazingly simple and stupid: all they can do is to mechanically shuffle zeros and ones around. What is the true potential of such automated computational devices? And what are the limits of what can be done by mechanical calculations? Understanding this kind of questions is ultimately what my research is about.

My research area, computational complexity theory, gives these deep and fascinating philosophical questions a crisp mathematical meaning. A computational problem is any task that is in principle amenable to being solved by a computer—i.e., it can be solved by mechanical application of mathematical steps. By constructing general, abstract models of computers we can study how to design efficient methods, or algorithms, for solving different tasks, but also prove mathematical theorems showing that some computational problems just cannot be solved efficiently for inherent reasons.

I am particularly interested in understanding different combinatorial optimization problems, which are of fundamental mathematical importance but also have wide-ranging applications in industry. My goal is, one the one hand, to prove formally that many such problems are beyond the reach of current algorithmic techniques, but also, on the other hand, to develop new algorithms that have the potential to go beyond the current state of the art.