This project studies randomized algorithms and derandomization techniques; specifically, randomized algorithms for on-line problems, randomized algorithms for graph connectivity questions, techniques for ``derandomizing'' (making deterministic) algorithms for on-line and connectivity problems, and general techniques for derandomizing large classes of randomized algorithms. An on-line problem is one in which the input is revealed to the algorithm only one piece at a time, and the algorithm is required to respond without knowledge of the future. An example is the problem of paging in a computer system: the operating system does not know which pages will be requested in the future, and therefore does not know which pages put in fast memory and which to leave in slow memory. Recent research has shown that randomized algorithms can be dramatically better than deterministic algorithms for some on-line motion planning, scheduling, and graph coloring. The (edge) connectivity of a connected graph is the minimum number of edges one has to remove to disconnect the graph. Determining the connectivity of a graph is an important problem in the area of network reliability. Recent advances have provided the key to faster algorithms to determine the edge connectivity of a graph. But the new algorithms are not likely to be the fastest possible algorithms. This research builds faster connectivity algorithms, randomized if necessary, deterministic if possible. Much research over the past few years has dealt with derandomizing randomized algorithms. This work continues this effort in the hope of derandomizing algorithms for certain on-line and connectivity problems, and also providing new general techniques for derandomizing randomized algorithms.
