NETCOM Research Group

IMDEA Networks’ PhD Student, Luis F. Chiroque, recently participated in an exclusive workshop in Wadern, Germany, in which the famous Graph Isomorphism Problem* and recent discoveries were discussed among 40 invited researchers from around the world.

IMDEA Networks was present at the workshop in which Dr. László Babai, a famous Hungarian Researcher and Professor in computer science and mathematics at the University of Chicago, presented his striking research results related to the Graph Isomorphism Problem (GI Problem). Dr. Babai has recently suggested a new algorithm for solving the problem. Compared to previous proposed solutions, his algorithm presents a complexity level that is only Quasi-polynomial. This is an important breakthrough, since the previous best result was nearly-exponential.  This means testing GI with large graphs might be speeded up from days to hours.

The GI Problem is one of the only natural computational problems in which complexity remains unsolved, and can very roughly be described as the problem of deciding whether two given graphs are structurally different or if one is simply an agitated version of the other. It is proving extremely difficult to reach agreement, as there are various communities with each their view on the problem and not least on its solution. Accordingly, just to mention some of these conflicting groups, we have practitioners, logicians, algorithmic group theorists, graph theorists, complexity theorists, and researchers and scientists from the combinatorial optimization area. These latter communities intend to apply different isomorphism techniques in their studies, thus adopting a practical approach to the theoretical problem. Research carried out at IMDEA Networks, among others by PhD Student Luis. F. Chiroque, is indeed based on such a practical approach to the theoretical problem (see the publications under more information below).

The workshop took place at Schloss Dagstuhl, Germany, an internationally renowned venue for informatics to exchange ideas and discuss their research findings. The event was an assembly point for more than 40 researchers from around the world, all working on the GI problem. Attendance was only by invitation. There were more than 20 talks in five days. Dr. László Babai gave two talks. First, he briefly explained the sketch of the algorithm, and then he moved on to speak in detail about other more specific issues of the problem. In the course of the workshop event, important differences between the theoretical and the practical approach emerged, not least it become clear that breakthroughs in theory are usually not reflected in practice. Thus, there is still a long way to go in this research field before a real solution can be established.

The event program permitted time to discuss current open problems such as String Isomorphism, Coset Intersection and their related sub-problems. Likewise, the attending researchers were invited to expose their current research activities in order to open up for a discussion and welcome new suggestions. Last, but not least, the event organization encouraged the participants to set up new collaborations among them.

* The Graph Isomorphism Problem is one of the only natural computational problems that remain unsolved, and can very roughly be described as the problem of deciding whether two given graphs are structurally different or if one is simply an agitated version of the other