New Algorithmic Complexity Bounds for Isomorphism Problems over Graphs and other Algebraic Structures

点击翻译按钮获取中文摘要

Isomorphism problems play a very important role in theoretical as well as practical algorithmic applications. The exact complexity classification of the Graph Isomorphism problem as wellas isomorphism problems for other algebraic structures has been elusive for several decades. The known techniques and standard complexity classes do not seem to be adequate to classify these problems.Several results obtained in the first part of the project improve the complexity classification of isomorphism problems following new approaches from areas like parameterized complexity or circuit theory. In the second part of the proposal we would like to continue thisline of research. On one hand we will further use tools and methods described in the first proposal, like parameterized complexity appliedto Hypergraph Isomorphism and restricted versions of Graph Isomorphism. Onon the other hand we plan to study isomorphism problemsfrom two new perspectives: the variations arising in the problem complexity when the inputs areprovided in a succinct way, and the connections of Graph Isomorphism withthe area of proof complexity.