Classical and Quantum Complexity of Graphisomorphism and Related Problems
Researchproject
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.