November 16, 2023. I. N. Ponomarenko (POMI). The Weisfeiler-Leman dimension and the isomorphism problem for concrete categories.

In this talk we consider the isomorphism problem for two kinds of concrete categories: finite groups and finite graphs. The problem consists in finding the most efficient algorithm that tests isomorphism for any two given objects of the category under consideration. The main open question here is the existence of an algorithm whose running time is at most a polynomial of the size of the objects to be tested for isomorphism. Proving the non-existence of such an algorithm would lead to a negative answer to the millennium problem P=NP.

The Weisfeiler-Leman dimension (introduced for groups and graphs in the last decade) can be viewed as a measure of the complexity of a given object in terms of the isomorphism problem. The talk will present equivalent definitions of this dimension arising in mathematical logic (the first-order logic with counting quantifiers), in algebra (the Schur rings), and in the analysis of algorithms (the multidimensional Weisfeiler-Leman algorithm). We discuss some recent results related to the Weisfeiler-Leman dimension and formulate some open questions.

List of talks at previous sessions of the seminar.