The Graph Isomorphism Problem†
Lecture in the summer term 2020
Tue, 08:30 - 10:00 am (AH II)
Thu, 2:30 - 04:00 pm (AH I)
Fr, 2:30† - 4:00 pm (AH III)
The question of whether there is a polynomial time algorithm deciding whether two graphs are isomorphic, known as the "graph isomorphism problem", has been one of the best known open problems in theoretical computer science for more than forty years. Indeed, the graph isomorphism problem is one of the very few natural problems in NP that is neither known to be in P nor known to be NP-complete. Remarkably, the problem has first been studied by chemists in the 1950s. Even though the problem is still open, researchers have obtained a number of substantial partial results. These results rely on a variety techniques from different branches of theoretical computer science and discrete mathematics. In this class, we will cover the highlights of forty years of research on the graph isomorphism problem, starting with early results from the 1970s to current research. Each of the results will be embedded in an introduction to the specific techniques and the context.
Thus on the one hand the class will give an in-depth treatment of a current research question in theoretical computer science. On the other hand, it spans a wide range of topics in algorithms, complexity theory, logic, graph theory, and group theory and conveys selective, yet deep insights into all these areas and the interaction among the areas.
Prerequisite for this course is a solid foundation in theoretical computer science and a successful completion of the required courses for the Bachelor in Computer Science such as "Data Structures and Algorithms" and "Computability and Complexity".†
The course will be held in english.
There will be weekly exercise sets. Completing these successfully, reaching at least 50% of possible points, is necessary for admittance to the examination.
There will be an exam. The exact modalities, including the possibility of an oral exam, will be announced later.