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.