Johannes Köbler: Complexity theory and a three-decade long collaboration
April 30, 2025 | Bharti Dharapuram
Johannes Köbler is a Professor of Theoretical Computer Science at the Humboldt University, Berlin who studies complexity theory and cryptography. He has been a regular visitor at IMSc since the 90s, making yearly excursions to collaborate on research problems.
Can you tell us about your broad area of research?
I mainly work on complexity theory, where we classify algorithmic problems based on the running time or space consumption sufficient to solve them. For each such upper bound, we get a complexity class. In the complexity class P (Polynomial Time), which is usually considered a class of feasible problems, we have all the problems that can be solved in polynomial running time. But there are some important problems where we do not know if they can be solved in polynomial time. Many of these problems belong to the class NP (Non-deterministic Polynomial Time), which has non-determinism. This means that we can easily check whether a proposed solution is correct, but finding a solution may be a hard problem.
For example, if we are given a graph with n vertices and we want to know whether it has a clique (subset of vertices that are all connected) of size k. If we are given k vertices in a graph, we can easily check whether they form a clique or not. But deciding whether such a clique exists is a hard problem and, in fact, NP-complete. A problem B in NP is said to be NP-complete if we can reduce any problem A in NP to B by transforming the instances of A in polynomial time into equivalent instances of B. We do not know if P = NP, or if these two classes of problems are different. If a problem is NP-complete, it can only be in P if all NP problems are in P. However, most researchers think that P is different from NP, that it is a proper subclass of NP.
Almost all problems in the class NP that are of relevance in practice either belong to P, meaning they are solvable in polynomial time, or they are NP-complete. Among the few problems in the class NP that are of practical interest and not known to be in P or NP-complete is the integer factorization problem, where an integer is factorized into its prime factors. It is clear that it is NP because given an integer n we can guess the factors and then verify if these really are the factors. Another such problem is graph isomorphism (whether two finite graphs can become equal after renaming their vertices). It is intermediate in that the problem is NP, but it is not known to be NP-complete and also not known to be P. There are some algorithms for graph isomorphism that run in sub-exponential and even in quasipolynomial time, which gives us some evidence that the problem is not NP-complete. We also have efficient heuristic algorithms for solving the graph isomorphism problem, which work well in most cases but may give the wrong answer in a few exceptions.
Earlier, I have also worked in learning theory. There we want, for example, to efficiently find a finite automata for a given regular language by asking specific questions about this language. Further, I'm interested in cryptography which also has connections to complexity theory. If we have some cryptographic system, a cipher for example, then it is important to prove lower bounds for breaking the system. And that is the main focus in complexity theory, to show lower bounds.
Can you tell us something about your academic journey and your association with IMSc?
We were taught informatics in high school but we only learnt how to program easy to solve problems. There was nothing about complexity theory really. But later at the University of Stuttgart in my undergraduate years, I took classes in complexity theory and liked it very much. I also did my PhD there and then moved to Ulm University for my postdoctoral research in Uwe Schöning's department. I think Arvind [V Arvind, retired faculty and former Director at IMSc] came to Ulm University in 1991, with a Humboldt fellowship and Uwe Schöning hosted him for one year. At that time we started collaborating and have been working together ever since.
I first came to IMSc in December 1994, to attend a workshop on ‘Algebraic Methods in Complexity Theory’ and the FSTTCS (Foundation of Software Technology and Theoretical Computer Science) conference. It was quite a different place then, there were almost no cars on the street with even cows grazing around.
My second visit to IMSc was for the FSTTCS Conference in 1999. Starting from this year we had a joint research project funded for 3 years by DST/DAAD on parameterized learning and a second one on the complexity of the graph isomorphism problem from 2004 to 2006. Moreover, from 2011 to 2017 our collaboration was supported by a grant from Humboldt Foundation which allowed us to finance mutual research visits for our PhD students in Chennai and Berlin. The collaboration with Arvind has sustained because we have similar interests, and because IMSc is very different from universities in Germany. Here, you mainly have PhD students and no undergraduates. I like this very much because you can spend all your time discussing scientific questions. I spend one or two months at IMSc on my visits. Back in Germany, I spend a lot of time teaching undergraduates and there is a greater load of administrative responsibilities.
Since 1999 I have been a Professor for Complexity and Cryptography at Humboldt University, Berlin. In 1989 I did my PhD at Stuttgart University with Uwe Schöning and afterwards I moved to Ulm University as a Postdoc where I finished my Habilitation in 1995.
Back Subscribe
