Parallel Max Cut Approximations

Given a graph with positive integer edge weights one may ask whether there exists an edge cut whose weight is bigger than a given number. This problem is NP-complete. We present here an approximation algorithm in NC which provides tight upper bounds to the proportion of edge cuts whose size is bigger than a given number. Our technique is based on the methods to convert randomized parallel algorithms into deterministic ones introduced by Karp and Wigderson. The basic idea of those methods is to replace an exponentially large sample space by one of polynomial size. In this work, we prove the interesting result that the statistical distance of random variables of the small sample space is bigger than the statistical distance of corresponding variables of the exponentially large space, which is the space of all edge cuts taken equiprobably