Computational complexity theory focuses on understanding capabilities of resource bounded computations. The broad goal of this project is to make original contributions to certain topics in computational complexity theory. Specifically, fundamental questions regarding the nature of unambiguous computations and average-case complexity will be investigated. In the topic of unambiguous computations, the role of unambiguity in small space computations will be investigated. In average-case complexity, the relations between average-case and the worst-case complexity of NP and various complexity classes that lie in the Polynomial-time Hierarchy, will be investigated.
Broader Impacts: This project addresses several basic questions in computational complexity theory. The results from this project will further our understanding of the nature of efficient computation. Since the notion of efficiency is central to all other areas of computing, this research has potential to scientifically impact these areas. Research results from this project will be published in peer-reviewed journals and will be presented at national and international conferences, thus enabling broad dissemination of the the results to enhance scientific understanding. New courses will be created and taught along the themes of this project, thus integrating teaching and research. The grant will also be used for various human resource development activities such as supporting and mentoring graduate students and inviting visitors.
