Dr. Pavan Aduri received a research grant from the US National Science Foundation, Collaborative Research: Research in Complexity Theory. This project is in collaboration with Dr. Vinodchandran Variyam from University of Nebraska, Lincoln.
Computational complexity theory seeks to understand the capabilities and limitations of resource bounded computations. This project focuses on two sub areas of the field--average-case complexity and unambiguous computations. Relations between the average-case complexity and the worst-case complexity of NP and various other complexity classes will be investigated. The computational complexity of certain matching and reachability problems will be studied with eye to understand the role of unambiguity in space-bounded computations.