Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-hard problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-bisection, k-vertex coloring, maximum independent set, etc. All these breakthroughs involve polynomial time randomized algorithms based upon semidefinite programming, a technique pioneered by Goemans and Williamson. In this paper, we give techniques to derandomize the above class of randomized algorithms, thus obtaining polynomial time deterministic algorithms with the same approximation ratios for the above problems. At the heart of our technique is the use of spherical symmetry to convert a nested sequence of n integrations, which cannot be approximated sufficiently well in polynomial time, to a nested sequence of just a constant number of integrations, which can be approximated sufficiently well in polynomial time.

Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-Complete problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-Bisection, k Vertex Coloring, Independent Set, etc. These breakthroughs all involve polynomial time randomized algorithms based upon semidefinite programming, a technique pioneered by M. Goemans and D. Williamson (1994). In this paper, we give techniques to derandomize the above class of randomized algorithms, thus obtaining polynomial time deterministic algorithms with the same approximation ratios for the above problems. Note that Goemans and Williamson also gave an elegant method to derandomize their Max-Cut algorithm. We show here that their technique has a fatal flaw. The techniques we subsequently develop are very different from theirs. At the heart of our technique is the use of spherical symmetry to convert a nested sequence of n integrations, which cannot be approximated sufficiently well in polynomial time, to a nested sequence of just a constant number of integrations, which can be approximated sufficiently well in polynomial time.

We are interested in understanding the exact power randomization provides to online algorithms.We study this problem in terms of computability, using the formulation of online problems