Project Details
Description
This project focuses on three problem areas in the theory of computational complexity. The first part aims at showing that in the context of computations which operate in limited work space, the use of randomness does not significantly increase computational power, with the goal of increasing our overall knowledge about the role of randomness as a tool in computation. The second part aims at ascertaining the computational limitations of small boolean circuits, with the goal of better understanding the aspects of computational problems that require more computational resources. The last part aims at improving the best known algorithms for exact solution of the fundamental graph coloring problem, with the larger goal of developing tools that may be more broadly applicable to speeding up wider classes of hard computational problems.***
Status | Finished |
---|---|
Effective start/end date | 6/1/97 → 5/31/01 |
Funding
- National Science Foundation: $174,779.00