This project is concerned with the design and analysis of randomized algorithms while treating randomness as a resource. Various techniques for reducing or eliminating the use of randomness in both parallel and sequential algorithms will be analyzed. The approach involves constructing sample spaces of sub-exponential size and then using efficient search techniques to reduce the number of random bits needed to sample from this space. A complementary approach is to study the interaction between specific pseudo-random generators and classes of algorithms. To identify the limitations of such techniques, trade-offs between the use of randomness and other resources such as space and time will be studied. An important part of the project is the application of techniques to the efficient solution of combinatorial problems which arise in fields such as computational geometry and learning theory. The use of randomness and probabilistic methods has led to significant theoretical developments in almost every area of computer science. However, there are no sources of true randomness and the cost of generating high-quality random bits is prohibitive. In this research a methodology for reducing the dependence of algorithms on randomness while maintaining their performance quality will be developed.
