Research on Complexity Theory, Algorithmic Number Theory.


Given a problem, can we realistically solve it using computers? Computational Complexity Theory aims to answer this question by describing the amount of resources required to solve the problem as a function of the input size. Those problems whose solution can be computed in time bounded by a polynomial in the size of the input are said to belong to the class P. By consensus, this is the class of problems considered efficiently solvable. Another intensely investigated class is the class NP consisting of search problems - problems for which the correctness of a given solution can be verified efficiently. A key result in complexity theory is the discovery of the phenomenon of NP-completeness. It involves the existence of certain problems in NP whose efficient solution would imply efficient solutions for all NP problems. Since then, most natural problems in NP have been classified as either being NP-complete or in P. Only a handful of problems in NP remain unclassified.

My research has been motivated by a fascination for these unclassified problems. Most such problems have a strong algebraic and/or number-theoretic flavour. These problems include(d) among others primality testing, integer factoring, polynomial factoring over finite fields, graph isomorphism, solvability of equations over finite fields and identity testing. Even within these problems there appears to be a wide variation in hardness: integer factoring is believed to be average-case hard and therefore suitable for cryptographic purposes, Graph Isomorphism appears to be easy on the average but may be hard in the worst-case, whereas polynomial factoring is believed to be efficiently solvable. During my doctoral study, I probed the complexity of these problems further. I discovered a common theme underlying many of these problems. More specifically, we showed that many of these problems were manifestations of the underlying problem of computing the automorphism group of a given ring. I also designed efficient algorithms for some of these problems.

Full Thesis:       ps       pdf