This project is a study of some problems in computational complexity theory, in particular some problems in structural complexity theory, and a number of algorithmic problems related to graph isomorphism.
In graph isomorphism, the investigator proposes to study further notions of coloring schemes, and in particular how such coloring schemes relate to graph spectra. We also wish to study a number of structural complexity theoretic questions as related to graph isomorphism and graph automorphism. It is expected that techniques of group theory, linear algebra, and combinatorics will interact in this study. The PI in collaboration with Prof. Osamu Watanabe have proposed a notion of stringent relativization, which is a generalization of the Karp-Lipton notion of advice strings. This study is related to circuit complexity theory and techniques of derandomization and algebraic techniques. We would like to develop this notion further. The investigator also proposes to study further a notion of persistent NP-hardness. We envision this to be an intermediate level of complexity measure between worst-case hardness and average-case complexity in the framework of Levin and others.
