Jakob Nordström is an Associate Professor at KTH Royal Institute of Technology in Stockholm, Sweden. His research is mainly focused on exploring the computational complexity of proving logic formulas. On the one hand, this task is believed to be intractable in the worst case, though deciding whether this is so is one of the famous million dollar Millennium Problems (the P vs. NP problem). On the other hand, today so-called SAT solvers are routinely and successfully used to solve large-scale formulas in a wide range of application areas, showing that here worst-case complexity is not a very helpful concept for understanding hardness in practice. In his research, Jakob Nordstrom tries to bridge this gap between theory and practice by employing tools from proof complexity to understand the theoretical power and limitations of different methods for reasoning about logic formulas (often leading to connections with other areas such as circuit complexity, communication complexity, or hardness of approximation), and to harness the strength of such methods algorithmically to build stronger SAT solvers that have the potential to go significantly beyond the current state of the art.
- Lower Bounds in Computational Complexity, Fall 2018. Visiting Scientist.