Technical Perspective: A Logical Step Toward the Graph Isomorphism Problem

The graph isomorphism problem remains one of those mysteries in theoretical computer science that fascinates laypersons and experts alike. In 1979, Garey and Johnson mentioned the problem in their renowned book on computers and intractability but, in fact, it dates back even earlier and has been unresolved for over half a century. In 2015, a major advance hit the media: Babai's quasipolynomial algorithm. This was the first improvement for the general problem in over 30 years. And yet it remains an open problem. Maybe surprisingly, there are various and quite distinct areas in which the problem finds applications.