Humboldt-Universität zu Berlin - Faculty of Mathematics and Natural Sciences - Complexity and Cryptography

Classical and Quantum Complexity of Graphisomorphism and Related Problems


Project supported by DAAD and DST.

Duration: 2003 to 2006

Project Leader: Prof. Johannes Köbler, Prof. V. Arvind

Research Background

The Graph Isomorphism problem of testing if two graphs are isomorphic is a well-studied algorithmic problem in the class NP. The objective of the project is to study the complexity of the Graph Isomorphism problem both in the classical and quantum computation models. The ultimate goal is, of course, to design efficient algorithms for the problem. Towards that goal the study of complexity theoretic issues of Graph Isomorphism and related group theoretic problems will be important progress. The best known algorithms for the problem, including Luks' polynomial time algorithm for bounded-degree graphs, Babai's work on bounded eigen-value graphs and other algorithms, all rely on algorithmic issues in group theory.