Certain computational problems such as graph connectivity, matching, and primality testing admit time-efficient algorithms. On the other hand problems such as boolean formula satisfiability, traveling salesman problem, and factoring still defy such fast algorithms. Why does such computational disparity exist among natural computational problems? This clearly is a foundational question which impacts many areas including mathematics, engineering, economics, optimization, and communication - areas beyond computer science. The main goal of "computational complexity theory'' is to study the notion of efficient computation. Typically, efficiency is measured in terms of computational resources such as time and memory (space).
This award will investigate certain central and longstanding open questions concerning nondeterminism and randomness in the context of memory-efficient computations. By focusing on memory-bounded computations, it will (a) study the role of unambiguity in nondeterminism (b) design deterministic algorithms that are simultaneously time and space efficient for nondeterministic computations (c) investigate the power of computations with multiple access to a random tape.
Study of proposed topics will help in understanding relations among three fundamental concepts of computation: determinism, nondeterminism and randomness, in the context of computations with limited memory. Intuition gained from this project will enhance our understanding of the complexity of solving practical computational problems arising from various fields beyond computer science. Research results from this grant will be published in peer-reviewed journals and will be presented at national and international conferences, thus enabling broad dissemination of the results to enhance scientific understanding. Expository survey articles aimed at a broader theoretical computer science audience will be written. New courses will be created and taught along the theme 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.
